Reorder Linked List in DSA Java - Execution Trace

Concept Flow - Reorder Linked List

Start at head

↓

Find middle node

→Split list into two halves

↓

Reverse second half

↓

Merge two halves alternately

↓

Done

The list is split into two halves at the middle, the second half is reversed, then both halves are merged by alternating nodes.

Execution Sample

DSA Java

ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
  slow = slow.next;
  fast = fast.next.next;
}
// Reverse from slow
// Merge two lists

This code finds the middle of the list, reverses the second half, then merges the two halves alternately.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with list	1 -> 2 -> 3 -> 4 -> 5 -> null	head points to 1	1 -> 2 -> 3 -> 4 -> 5 -> null
2	Find middle node using slow and fast pointers	1 -> 2 -> 3 -> 4 -> 5 -> null	slow moves to 2, fast moves to 3	1 -> 2 -> 3 -> 4 -> 5 -> null
3	Continue finding middle	1 -> 2 -> 3 -> 4 -> 5 -> null	slow moves to 3, fast moves to 5	1 -> 2 -> 3 -> 4 -> 5 -> null
4	Fast pointer reached end, slow at middle	1 -> 2 -> 3 -> 4 -> 5 -> null	slow at 3 (middle)	1 -> 2 -> 3 -> 4 -> 5 -> null
5	Split list into two halves	First half: 1 -> 2 -> 3 -> null Second half: 4 -> 5 -> null	slow.next set to null to split	1 -> 2 -> 3 -> null and 4 -> 5 -> null
6	Reverse second half	4 -> 5 -> null	prev = null, curr = 4 curr.next changed to prev	4 -> null
7	Second half reversed fully	5 -> 4 -> null	curr = null, prev = 5	5 -> 4 -> null
8	Merge two halves alternately	First half: 1 -> 2 -> 3 -> null Second half: 5 -> 4 -> null	1.next = 5, 5.next = 2	1 -> 5 -> 2 -> 3 -> null and 4 -> null
9	Continue merging	Remaining nodes: 2 -> 3 -> null and 4 -> null	2.next = 4, 4.next = 3	1 -> 5 -> 2 -> 4 -> 3 -> null
10	Merging complete	1 -> 5 -> 2 -> 4 -> 3 -> null	No more nodes in second half	1 -> 5 -> 2 -> 4 -> 3 -> null
11	End	Reordered list	head points to 1	1 -> 5 -> 2 -> 4 -> 3 -> null

💡 All nodes merged alternately, second half exhausted

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	After Step 8	Final
slow	1	2	3	3	3	3	3
fast	1	3	5	5	5	5	5
head	1	1	1	1	1	1	1
prev (reverse)	null	null	null	null	4	5	5
curr (reverse)	4	4	4	4	5	null	null

Key Moments - 3 Insights

Why do we split the list at the middle node slow.next = null?

Splitting at slow.next = null breaks the list into two separate lists so we can reverse the second half independently. See step 5 in execution_table.

Why do we reverse the second half before merging?

Reversing the second half allows us to merge nodes from the end of the original list alternately with nodes from the start. See steps 6 and 7.

How do we merge two lists alternately without losing nodes?

We carefully update next pointers step-by-step, linking one node from first half, then one from second half, preserving the rest. See steps 8 and 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, where is the slow pointer?

A At node 2

B At node 4

C At node 3

D At node 5

💡 Hint

Check the 'Pointer Changes' column at step 4 in execution_table

At which step does the second half get fully reversed?

A Step 7

B Step 6

C Step 5

D Step 8

💡 Hint

Look for when curr becomes null and prev points to reversed list in execution_table

If we do not split the list at slow.next = null, what would happen during merging?

A The list would merge correctly

B Merging would create cycles or incorrect links

C The second half would not reverse

D The first half would be lost

💡 Hint

Refer to step 5 and 8 in execution_table about splitting and merging

Concept Snapshot

Reorder Linked List:
1. Find middle with slow/fast pointers
2. Split list into two halves
3. Reverse second half
4. Merge halves alternately
Result: L0→Ln→L1→Ln-1→L2→Ln-2→…

Full Transcript

To reorder a linked list, first find the middle node using slow and fast pointers. Then split the list into two halves by setting slow.next to null. Reverse the second half of the list. Finally, merge the two halves by alternating nodes from each half. This creates the reordered list where nodes from the start and end alternate. The execution table shows each step with pointer changes and the list state. Key moments include why splitting is needed, why reversing is done, and how merging preserves nodes. The visual quiz tests understanding of pointer positions and effects of splitting.

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