Reorder Linked List in DSA Java

Mental Model

We rearrange a linked list so nodes alternate from start and end towards the center.

Analogy: Imagine lining up people from two ends of a line, taking one from the front, then one from the back, and repeating until everyone is rearranged.

1 -> 2 -> 3 -> 4 -> 5 -> null
↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5 -> null

Goal: Rearrange to 1 -> 5 -> 2 -> 4 -> 3 -> null

Step 1: Find middle node using slow and fast pointers

1 -> 2 -> 3 -> 4 -> 5 -> null
          ↑ slow, ↑↑ fast

Why: We split the list into two halves at the middle to reorder

Step 2: Split list into two halves: first half 1->2->3, second half 4->5

First half: 1 -> 2 -> 3 -> null
Second half: 4 -> 5 -> null

Why: Separating halves allows reversing second half for merging

Step 3: Reverse second half: 4 -> 5 -> null becomes 5 -> 4 -> null

First half: 1 -> 2 -> 3 -> null
Second half reversed: 5 -> 4 -> null

Why: Reversing second half helps alternate nodes from front and back

Step 4: Merge nodes alternately from first and reversed second half

1 -> 5 -> 2 -> 4 -> 3 -> null

Why: Alternating nodes from both halves achieves the reorder

Result:

1 -> 5 -> 2 -> 4 -> 3 -> null

Annotated Code

DSA Java

public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        // Find middle of list
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next; // advance slow by 1
            fast = fast.next.next; // advance fast by 2
        }

        // Split and reverse second half
        ListNode second = slow.next;
        slow.next = null; // break first half
        second = reverseList(second);

        // Merge two halves
        ListNode first = head;
        while (second != null) {
            ListNode tmp1 = first.next;
            ListNode tmp2 = second.next;

            first.next = second; // link first to second
            second.next = tmp1; // link second to next of first

            first = tmp1; // move first forward
            second = tmp2; // move second forward
        }
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev; // reverse pointer
            prev = curr; // move prev forward
            curr = nextTemp; // move curr forward
        }
        return prev;
    }

    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        Solution sol = new Solution();
        sol.reorderList(head);
        printList(head);
    }
}

while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }

Find middle node by moving slow 1 step and fast 2 steps

slow.next = null;

Split list into two halves by breaking link at middle

second = reverseList(second);

Reverse second half to prepare for merging

while (second != null) { ... first.next = second; second.next = tmp1; first = tmp1; second = tmp2; }

Merge nodes alternately from first and reversed second half

curr.next = prev; prev = curr; curr = nextTemp;

Reverse pointers in second half

Output

1 -> 5 -> 2 -> 4 -> 3 -> null

Complexity Analysis

Time: O(n) because we traverse the list multiple times but each node is visited a constant number of times

Space: O(1) because we reorder the list in place without extra data structures

vs Alternative: Compared to creating a new list or array to reorder, this approach uses no extra space and is more efficient

Edge Cases

Empty list

Function returns immediately without changes

DSA Java

if (head == null || head.next == null) return;

Single node list

Function returns immediately without changes

DSA Java

if (head == null || head.next == null) return;

List with two nodes

No reorder needed, list remains the same

DSA Java

while (fast.next != null && fast.next.next != null) { ... }

When to Use This Pattern

When asked to reorder a linked list alternating from front and back, use the pattern of finding the middle, reversing the second half, then merging.

Common Mistakes

Mistake: Not breaking the list into two halves before reversing second half
Fix: Set slow.next = null to split the list before reversing

Mistake: Merging without updating pointers correctly causing cycles or lost nodes
Fix: Save next pointers before re-linking and update pointers carefully in merge loop

Summary

Rearranges a linked list so nodes alternate from start and end towards the center.

Use when you need to reorder a list in a specific alternating pattern without extra space.

The key is to split the list, reverse the second half, then merge nodes alternately.

Practice

1. What is the main goal of the Reorder Linked List problem?

easy

A. Sort the linked list in ascending order

B. Rearrange the list so nodes alternate from start and end towards the center

C. Reverse the entire linked list

D. Remove duplicate nodes from the linked list

Solution

1. Step 1: Understand the problem requirement

   The problem asks to reorder the list so that nodes come alternately from the start and end, like L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 ...

2. Step 2: Differentiate from other operations

   This is not sorting or reversing the whole list, but a specific rearrangement pattern.

3. Final Answer:

   Rearrange the list so nodes alternate from start and end towards the center -> Option B

4. Quick Check:

   Reorder = alternate start/end nodes [OK]

Hint: Think of weaving nodes from front and back alternately [OK]

Common Mistakes:

• Confusing reorder with sorting
• Trying to reverse the whole list only
• Ignoring the alternating pattern

2. Which Java code snippet correctly splits a linked list into two halves using slow and fast pointers?

easy

A. ListNode slow = head, fast = head; while(fast.next != null) { slow = slow.next; fast = fast.next; }

B. ListNode slow = head.next, fast = head; while(fast != null) { slow = slow.next; fast = fast.next.next; }

C. ListNode slow = head, fast = head; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

D. ListNode slow = head, fast = head.next; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

Solution

1. Step 1: Initialize pointers correctly

   Slow starts at head, fast starts at head.next to find middle for even length lists.

2. Step 2: Loop condition and pointer moves

   Loop while fast and fast.next are not null, move slow by one and fast by two nodes.

3. Final Answer:

   ListNode slow = head, fast = head.next; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } -> Option D

4. Quick Check:

   Slow at middle, fast moves twice [OK]

Hint: Start fast one step ahead to split even lists correctly [OK]

Common Mistakes:

• Starting fast at head causing wrong middle
• Incorrect loop conditions causing null pointer
• Moving fast by one instead of two

3. Given the linked list 1 -> 2 -> 3 -> 4 -> 5 -> null, what is the reordered list after applying the reorder algorithm?

medium

A. 1 -> 5 -> 2 -> 4 -> 3 -> null

B. 5 -> 4 -> 3 -> 2 -> 1 -> null

C. 1 -> 2 -> 3 -> 4 -> 5 -> null

D. 1 -> 3 -> 5 -> 2 -> 4 -> null

Solution

1. Step 1: Identify nodes from start and end

   Start with 1 (head), then last node 5, then second node 2, then second last 4, then middle 3.

2. Step 2: Arrange nodes alternately

   Link nodes in order: 1 -> 5 -> 2 -> 4 -> 3 -> null.

3. Final Answer:

   1 -> 5 -> 2 -> 4 -> 3 -> null -> Option A

4. Quick Check:

   Alternate front and back nodes [OK]

Hint: Pick nodes alternately from front and back [OK]

Common Mistakes:

• Reversing entire list instead of reordering
• Skipping middle node placement
• Mixing node order incorrectly

4. Consider this buggy code snippet for reversing the second half of a linked list in reorder operation:

ListNode prev = null;
ListNode curr = mid.next;
while(curr != null) {
  ListNode nextTemp = curr.next;
  curr.next = prev;
  prev = curr;
  curr = nextTemp;
}
mid.next = prev;

What is the likely bug here?

medium

A. The prev pointer is not initialized correctly

B. The loop condition should be while(curr.next != null)

C. The mid.next should be set to null before reversing

D. The reversal logic is correct; no bug present

Solution

1. Step 1: Understand reversal impact on original list

   Before reversing second half, mid.next should be set to null to break the list and avoid cycles.

2. Step 2: Identify missing step causing cycle

   Without setting mid.next = null before reversal, the list may form a cycle causing infinite loops later.

3. Final Answer:

   The mid.next should be set to null before reversing -> Option C

4. Quick Check:

   Break list before reverse to avoid cycles [OK]

Hint: Always cut list at middle before reversing second half [OK]

Common Mistakes:

• Not breaking list causing infinite loops
• Changing loop condition incorrectly
• Misinitializing pointers

5. You have a linked list with nodes 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null. After reordering, what will be the final list?

hard

A. 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null

B. 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

C. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

D. 1 -> 3 -> 5 -> 2 -> 4 -> 6 -> null

Solution

1. Step 1: Split list into two halves

   First half: 1 -> 2 -> 3, second half: 4 -> 5 -> 6.

2. Step 2: Reverse second half

   Reversed second half: 6 -> 5 -> 4.

3. Step 3: Merge halves alternately

   Merge nodes alternately: 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null.

4. Final Answer:

   1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null -> Option A

5. Quick Check:

   Alternate front and reversed back nodes [OK]

Hint: Reverse second half, then weave nodes alternately [OK]

Common Mistakes:

• Not reversing second half before merging
• Merging nodes in wrong order
• Forgetting to terminate list properly