Problem

You are given the head of a singly linked-list. The list can be represented as:

$$ L_0 → L_1 → … → L_{n - 1} → L_n $$

Reorder the list to be on the following form::

$$ L_0 → L_n → L1 → L_{n - 1} → L2 → L_{n - 2} → … $$

Examples

Example 1:

---
title: Input List
---
graph LR
	A1[1] --> B2[2] --> C3[3] --> D4[4]
  
---
title: Output
---
 graph LR
   A1[1] --> D4[4] --> B2[2] --> C3[3]
  
1
2

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

---
title: Input List
---
 graph LR
   A1[1] --> B2[2] --> C3[3] --> D4[4] --> E5[5]
  
---
title: Outpu
---
 graph LR
   A1[1] --> E5[5] --> B2[2] --> D4[4] --> C3[3]
  
1
2

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Solution

This problem is not straightforward, because it requires “in-place” operations. That means we can only change their pointers, not creating a new list.

Method 1 - Break the List and Reverse Second Half

This problem can be solved by following these steps:

  1. Break the list in the middle into two halves using fast and slow pointers.
  2. Reverse the second half of the list.
  3. Merge the two halves back together.

For example, given the input list:

  • 1->2->3->4->5->6->7->8
  • After breaking: List A: 1->2->3->4 and List B: 5->6->7->8
  • Reverse List B: 8->7->6->5
  • Merge them into: 1->8->2->7->3->6->4->5

The method works for both even and odd-length lists. For instance, if the list has an odd number of nodes, such as 5, the first part will have 3 nodes and the second part will have 2 nodes, and the solution will still be valid.

There is no need to return anything since we perform the operations in place.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

class Solution {
    public void reorderList(ListNode head) {
		if (head == null || head.next == null || head.next.next == null) {
			return;
		}
	
		ListNode middle = getMidNode(head);
		ListNode second = middle.next;
	
		middle.next = null; // split the list
	
		second = reverseIterative(second);
	
		ListNode first = head;
	
		ListNode curr1 = first;
		ListNode curr2 = second;
	
		// second will be equal or less than first in length
		// so iterate on curr2
		while (curr2 != null) {
			ListNode temp1 = curr1.next;
			ListNode temp2 = curr2.next;
	
			curr1.next = curr2;
			curr2.next = temp1;
	
			curr1 = temp1;
			curr2 = temp2;
		}        
    }
	public ListNode getMidNode(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode slow = head;
		ListNode fast = head;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
	
	public ListNode reverseIterative(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode prev = null;
		ListNode curr = head;
		while (curr != null) {
			ListNode next = curr.next;
			curr.next = prev;
			prev = curr;
			curr = next;
		}
		return prev;
	}    
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list. Here’s the breakdown:
    • Finding the middle node: O(n)
    • Reversing the second half: O(n)
    • Merging the two halves: O(n)
  • 🧺 Space complexity: O(1), since we only use a constant amount of extra space for the pointers and variables.