Given a singly linked list L : L[0] -> L[1] -> … -> L[N-1] -> L[N]. Reorder it to : L[0] -> L[N] -> L[1] -> L[N-1] -> L[2] -> L[N-2] -> …
Solution
First, we find the middle node of list L. We can use two pointers, fast and slow, both initialized with head pointer of list L, to find the middle node in one-pass. Every time the slow pointer moves one step, the fast pointer moves two step. So when the fast pointer or its next reaches the end, the slow pointer is at the middle node.
Second, we cut list L into two halves, L1 and L2. L1 ends at the middle node and L2 starts at the next node of the middle node. Then we reverse L2, and we use L3 to denote the reversed list.
Third, we merge L1 and L3.
The time and space complexities are O(N) and O(1), respectively.