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 and fast.


Analysis written by: @awice.