Solution: Reorder List

Statement

Given the head of a singly linked list, reorder the list as if it were folded on itself. For example, if the list is represented as follows:

$L_{0}$ → $L_{1}$ → $L_{2}$ → … → $L_{n-2}$ → $L_{n-1}$ → $L_{n}$ ​

This is how you’ll reorder it:

$L_{0}$ → $L_{n}$ → $L_{1}$ → $L_{n - 1}$ → $L_{2}$ → $L_{n - 2}$ → …

You don’t need to modify the values in the list’s nodes; only the links between nodes need to be changed.

Constraints:

• The range of number of nodes in the list is $[1, 500]$.
• $-5000 \leq$ Node.value $\leq 5000$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach for this problem is to traverse the complete linked list twice. First, we need to start from the first node using the current pointer. To find the last node, we traverse the complete linked list and add the last node in front of the current node. After adding the last node, the current node will move to the next node. Each time the last node is added, the current node will move ahead in the list. For this reason we need to find the last node. To do that, we’ll need to find the last occurring nodes $n$ times, which will take $O(n)$ time complexity to find the last node each time. We’ll end the program when both current and last nodes become equal.

The total time complexity for this solution is $O(n^2)$, which is way too much. However, the space complexity of this naive approach is $O(1)$ as we used the constant extra space.

Optimized approach using in-place manipulation of a linked list

The essence of this approach lies in reorganizing a linked list in three main steps. It begins by using two pointers at different speeds to locate the middle of the list: one moves step by step, and the other two steps at a time. The faster one reaches the end, the slower one is right in the middle. Then, after reaching the middle, the second half of the list is reversed. This means each node of the list now points back to the one before it, effectively flipping the order of this half. The final step merges the two halves together. Starting with the heads of each half, the nodes from the reversed second half are linked and alternated with those from the first half. This is done by adjusting the next pointers: each node in the first half now points to a node from the second half, and similarly, each node from the second half is linked to the subsequent node from the first half. The algorithm performed all steps without using extra space.

We can use two pointers, first and second, to point to the heads of the two halves of the linked list. We’ll traverse both halves in lockstep to merge the two linked lists, interleaving the nodes from the second half into the first half.

The slides below illustrate how we want the algorithm to run: