Solution: Reorder List

Let's solve the Reorder List problem using the In-Place Manipulation of a Linked List pattern.

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:

L0L_{0}L1L_{1}L2L_{2} → … → Ln2L_{n-2}Ln1L_{n-1}LnL_{n}

This is how you’ll reorder it:

L0L_{0}LnL_{n}L1L_{1}Ln1L_{n - 1}L2L_{2}Ln2L_{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][1, 500].
  • 5000-5000 \leq Node.value 5000\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 nn times, which will take O(n)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(n2)O(n^2), which is way too much. However, the space complexity of this naive approach is O(1)O(1) as we used the constant extra space.

Optimized approach using in-place manipulation of a linked list

We need to perform the in-place reversal for the second half of the linked list, which will allow us to not use any extra memory. To solve the original problem, we can use the modified in-place methodology after the first in-place reversal to merge the two halves of the linked list. We can use two-pointers, firstfirst and secondsecond, 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:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.