Solution: Reorder List

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

We'll cover the following

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} → … → Ln−2L_{n-2} → Ln−1L_{n-1} → LnL_{n} ​

This is how you’ll reorder it:

L0L_{0} → LnL_{n} → L1L_{1} → Ln−1L_{n - 1} → L2L_{2} → Ln−2L_{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

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:

Let’s go over the steps in detail:

Find the middle node:

We use two pointers to find the middle node, slow and fast.

  • The slow pointer moves one step at a time: slow = slow.next.
  • The fast pointer moves two steps at a time: fast = fast.next.next.

This way when the fast pointer reaches the end of the LinkedList, the slow pointer points at the middle node.

Reverse the second part of the list:

  1. We traverse the list from the middle node till the end of the linked list using the slow pointer.

  2. We save the neighbors of each node.

  3. The prev pointer points at the previous node and tmp points at curr.next.

While moving through the linked list, we point curr.next at prev. Then shift the current node to the right for the next iteration, prev = curr and curr = tmp.

Merge lists:

  1. We start by taking the first node of the first and second half of the linked list. Let’s call them first and second respectively. We also save their successors.

  2. While traversing the list, we set first.next = second, and point second.next at the successor of the first node. The first iteration is completed here.

  3. Now we move to the successors of the previously saved nodes for the next iteration.

Let’s look at the solution code:

main.java
LinkedListNode.java
LinkedList.java
PrintList.java
class Reorder {
	public static LinkedListNode reorderList(LinkedListNode head)
	{
		if(head == null)
		    return head;
		LinkedListNode slow = head; 
		LinkedListNode fast = head;
		while(fast!= null && fast.next != null)
		{
			slow = slow.next;
			fast = fast.next.next;
		}
		LinkedListNode prev = null;
		LinkedListNode curr = slow;
		LinkedListNode next = null;
		while(curr != null)
		{
			next = curr.next;
			curr.next = prev;
			prev = curr;
			curr = next;
		}
		LinkedListNode first = head;
		LinkedListNode second = prev;
		LinkedListNode temp = head;
        while(second.next != null)
		{
			temp = temp.next;
			first.next = second;
			second = second.next;
			first.next.next = temp;
			first = first.next.next;
		}
		return head;
	}
  
  // Driver code
	public static void main(String[] args) {
		LinkedList obj1 = new LinkedList();
		int[] inputList = {1, 1, 2, 2, 3, -1, 10, 12};
		obj1.createLinkedList(inputList);
		System.out.print("1.\tOriginal list: ");
		PrintList.printListWithForwardArrow(obj1.head);
		reorderList(obj1.head);
		System.out.print("\tAfter folding: ");
        PrintList.printListWithForwardArrow(obj1.head);
		System.out.println(PrintHyphens.repeat("-", 100));
		LinkedList obj2 = new LinkedList();
		int[] inputList1 = {10, 20, -22, 21, -12};
		obj2.createLinkedList(inputList1);
		System.out.print("2.\tOriginal list: ");
		PrintList.printListWithForwardArrow(obj2.head);
		reorderList(obj2.head);
		System.out.print("\tAfter folding: ");
        PrintList.printListWithForwardArrow(obj2.head);
		System.out.println(PrintHyphens.repeat("-", 100));
		LinkedList obj3 = new LinkedList();
		int[] inputList2 = {1, 1, 1};
		obj3.createLinkedList(inputList2);
		System.out.print("3.\tOriginal list: ");
		PrintList.printListWithForwardArrow(obj3.head);
		reorderList(obj3.head);
		System.out.print("\tAfter folding: ");
        PrintList.printListWithForwardArrow(obj3.head);
		System.out.println(PrintHyphens.repeat("-", 100));
		LinkedList obj4 = new LinkedList();
		int[] inputList3 = {-2, -5, -6, 0, -1, -4};
		obj4.createLinkedList(inputList3);
		System.out.print("4.\tOriginal list: ");
		PrintList.printListWithForwardArrow(obj4.head);
		reorderList(obj4.head);
		System.out.print("\tAfter folding: ");
        PrintList.printListWithForwardArrow(obj4.head);
		System.out.println(PrintHyphens.repeat("-", 100));
		LinkedList obj5 = new LinkedList();
		int[] inputList4 = {3, 1, 5, 7, -4, -2, -1, -6};
		obj5.createLinkedList(inputList4);
		System.out.print("5.\tOriginal list: ");
		PrintList.printListWithForwardArrow(obj5.head);
		reorderList(obj5.head);
		System.out.print("\tAfter folding: ");
        PrintList.printListWithForwardArrow(obj5.head);
		System.out.println(PrintHyphens.repeat("-", 100));
	}
}
Reorder List

Solution summary

To recap, the solution to this problem can be divided into the following three parts:

  1. Find the middle node. If there are two middle nodes, then choose the second node.
  2. Reverse the second half of the linked list.
  3. Merge both halves of the linked lists alternatively.

Time complexity

The time complexity of this solution is linear, O(n)O(n), where nn is the number of nodes in a linked list.

Space complexity

The space complexity of the solution is constant, O(1)O(1).

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