Solution
Approach 1: Output to Array
Intuition and Algorithm
Put every node into an array A
in order. Then the middle node is just A[A.length // 2]
, since we can retrieve each node by index.
Complexity Analysis

Time Complexity: , where is the number of nodes in the given list.

Space Complexity: , the space used by
A
.
Approach 2: Fast and Slow Pointer
Intuition and Algorithm
When traversing the list with a pointer slow
, make another pointer fast
that traverses twice as fast. When fast
reaches the end of the list, slow
must be in the middle.
Complexity Analysis

Time Complexity: , where is the number of nodes in the given list.

Space Complexity: , the space used by
slow
andfast
.
Analysis written by: @awice.