Reorder Linked List in DSA Java - Time & Space Complexity

Time Complexity: Reorder Linked List

O(n)

Understanding Time Complexity

We want to understand how the time needed to reorder a linked list changes as the list grows.

Specifically, how the steps increase when we rearrange nodes from start and end alternately.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    
    // Find middle
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Reverse second half
    ListNode prev = null, curr = slow;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }

    // Merge two halves
    ListNode first = head, second = prev;
    while (second != null && first != null && second != first && second.next != first) {
        ListNode temp1 = first.next;
        ListNode temp2 = second.next;
        first.next = second;
        second.next = temp1;
        first = temp1;
        second = temp2;
    }
}

This code reorders a linked list by first finding the middle, reversing the second half, then merging nodes alternately from each half.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Three main loops: one to find the middle, one to reverse the second half, and one to merge the halves.
• How many times: Each loop runs roughly n/2 times, where n is the number of nodes.

How Execution Grows With Input

As the list size grows, each step processes about half the list, so total steps grow roughly in a straight line with n.

Input Size (n)	Approx. Operations
10	About 30 steps (3 loops x ~5 each)
100	About 150 steps (3 loops x ~50 each)
1000	About 1500 steps (3 loops x ~500 each)

Pattern observation: The total steps increase linearly as the list size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to reorder grows directly in proportion to the number of nodes in the list.

Common Mistake

[X] Wrong: "Reversing the second half or merging halves takes more than linear time because it looks like nested loops."

[OK] Correct: Each loop runs separately over different parts of the list, not nested inside each other, so total time adds up linearly, not multiplies.

Interview Connect

Understanding this linear time complexity helps you explain how to efficiently reorder linked lists, a common skill in coding interviews.

Self-Check

"What if we used recursion to merge the two halves instead of a loop? How would the time complexity change?"

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