Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Reorder List

Reorder List

Master this topic with zero to advance depth.

Reorder List

You are given the head of a singly linked-list. The list can be represented as: L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form: L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Visual Representation

List: 1 -> 2 -> 3 -> 4 1. Find middle: 2 2. Reverse second half: 4 -> 3 3. Merge lists: 1 -> 4 -> 2 -> 3
Medium

Examples

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

Level I: Brute Force (Array/Stack)

Intuition

Store all nodes in an array. Use two pointers (start and end) to reorder the nodes by changing their next pointers.

⏱ O(N)💾 O(N)

Detailed Dry Run

1->2->3->4. Array: [1, 2, 3, 4].

  1. 1.next = 4.
  2. 4.next = 2.
  3. 2.next = 3.
  4. 3.next = null.
java
public void reorderList(ListNode head) {
    if (head == null) return;
    List<ListNode> nodes = new ArrayList<>();
    while (head != null) {
        nodes.add(head);
        head = head.next;
    }
    int i = 0, j = nodes.size() - 1;
    while (i < j) {
        nodes.get(i).next = nodes.get(j);
        i++;
        if (i == j) break;
        nodes.get(j).next = nodes.get(i);
        j--;
    }
    nodes.get(i).next = null;
}

⚠️ Common Pitfalls & Tips

O(N) space makes this less efficient than in-place methods.

Visual Trace (Array/Stack)

List: 1 -> 2 -> 3 -> 4 Array: [1, 2, 3, 4] i=0, j=3: 1.next=4, 4.next=2 i=1, j=2: 2.next=3 i=2, j=2: Break. 3.next=null Result: 1 -> 4 -> 2 -> 3
Approach 2

Level II: Using a Stack

Intuition

Store all nodes in a stack. Since a stack is LIFO, popping from it gives nodes from the end. Only pop N/2 nodes and interleave them with the first half of the list.

⏱ O(N)💾 O(N)

Detailed Dry Run

1->2->3->4. Stack: [1, 2, 3, 4].

  1. Pop 4, link after 1: 1->4->2.
  2. Pop 3, link after 2: 1->4->2->3. Wait, stop after N/2 swaps.
java
public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    Stack<ListNode> stack = new Stack<>();
    ListNode curr = head;
    while (curr != null) { stack.push(curr); curr = curr.next; }
    int n = stack.size();
    curr = head;
    for (int i = 0; i < n / 2; i++) {
        ListNode next = curr.next;
        ListNode last = stack.pop();
        curr.next = last;
        last.next = next;
        curr = next;
    }
    curr.next = null;
}

⚠️ Common Pitfalls & Tips

Be careful to set the final next pointer to null to prevent cycles.

Approach 3

Level III: Optimal (Middle + Reverse + Merge)

Intuition

Find the middle of the list. Reverse the second half. Merge the two halves one by one.

⏱ O(N)💾 O(1)

Detailed Dry Run

1->2->3->4.

  1. Mid: 2.
  2. Reverse 3->4 to 4->3.
  3. Merge (1->2) and (4->3): 1->4->2->3.
java
public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    ListNode prev = null, curr = slow.next; slow.next = null;
    while (curr != null) {
        ListNode tmp = curr.next; curr.next = prev; prev = curr; curr = tmp;
    }
    ListNode first = head, second = prev;
    while (second != null) {
        ListNode tmp1 = first.next, tmp2 = second.next;
        first.next = second; second.next = tmp1;
        first = tmp1; second = tmp2;
    }
}

⚠️ Common Pitfalls & Tips

Ensure to cut the list at the middle (slow.next = null) to avoid cycles.

← Previous QuestionMiddle of the Linked List
Next Question →Copy List with Random Pointer