Reorder Linked List in DSA C - 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

↓

Reordered list 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 C

void reorderList(Node* head) {
  Node* mid = findMiddle(head);
  Node* second = reverseList(mid->next);
  mid->next = NULL;
  mergeLists(head, second);
}

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

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with full list	1->2->3->4->5->NULL	head points to 1	1 -> 2 -> 3 -> 4 -> 5 -> NULL
2	Find middle node	1->2->3->4->5->NULL	mid points to 3	1 -> 2 -> 3(mid) -> 4 -> 5 -> NULL
3	Split list at middle	First half: 1->2->3->NULL Second half: 4->5->NULL	mid->next set to NULL	1 -> 2 -> 3 -> NULL 4 -> 5 -> NULL
4	Reverse second half	Second half reversed: 5->4->NULL	second points to 5	1 -> 2 -> 3 -> NULL 5 -> 4 -> NULL
5	Merge two halves alternately	Merged list: 1->5->2->4->3->NULL	Pointers rearranged to alternate nodes	1 -> 5 -> 2 -> 4 -> 3 -> NULL
6	End	Reordered list complete	No pointer changes	1 -> 5 -> 2 -> 4 -> 3 -> NULL

💡 All nodes merged alternately, list reordered successfully.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
head	points to 1	points to 1	points to 1	points to 1	points to 1	points to 1
mid	NULL	points to 3	points to 3	points to 3	points to 3	points to 3
second	NULL	NULL	points to 4	points to 5	points to 5	points to 5
list size	5 nodes	5 nodes	3 nodes + 2 nodes	3 nodes + 2 nodes	5 nodes merged	5 nodes merged

Key Moments - 3 Insights

Why do we split the list at the middle node and set mid->next to NULL?

Splitting at the middle breaks the list into two separate halves so we can reverse the second half independently. Setting mid->next to NULL ends the first half properly, preventing cycles during merging. See execution_table step 3.

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, achieving the reorder pattern. See execution_table step 4.

How does merging alternate nodes work without losing any nodes?

We take one node from the first half, then one from the reversed second half, adjusting pointers carefully to link them alternately. This continues until all nodes are merged. See execution_table step 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, which node does 'mid' point to?

A Node with value 2

B Node with value 3

C Node with value 4

D Node with value 5

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 2.

At which step does the second half of the list get reversed?

A Step 5

B Step 3

C Step 4

D Step 6

💡 Hint

Look for the operation 'Reverse second half' in the execution_table.

If we did not set mid->next to NULL at step 3, what would happen during merging?

A The list would become cyclic or have incorrect links.

B The second half would not reverse properly.

C The list would merge correctly without issues.

D The middle node would be lost.

💡 Hint

Refer to the explanation in key_moments about splitting the list and pointer changes at step 3.

Concept Snapshot

Reorder Linked List:
1. Find middle node using slow/fast pointers.
2. Split list into two halves at middle.
3. Reverse second half.
4. Merge halves alternately.
Result: nodes reordered as first, last, second, second last, etc.

Full Transcript

To reorder a linked list, we first find the middle node to split the list into two halves. We then reverse the second half so that we can merge nodes from the start and end alternately. After splitting, we set the middle node's next pointer to NULL to separate the halves. We then merge the two halves by alternating nodes from each half, adjusting pointers carefully. This process results in a reordered list where nodes appear in the order of first, last, second, second last, and so on.

Practice

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

easy

A. To rearrange the list so nodes alternate from start and end

B. To sort the linked list in ascending order

C. To reverse the entire linked list

D. To remove duplicate nodes from the list

Solution

1. Step 1: Understand the reorder pattern

   The reorder linked list operation rearranges nodes so that the first node is followed by the last node, then the second node, then the second last node, and so on.

2. Step 2: Differentiate from other operations

   This is different from sorting, reversing, or removing duplicates because it mixes nodes from start and end alternatively.

3. Final Answer:

   To rearrange the list so nodes alternate from start and end -> Option A

4. Quick Check:

   Reorder = alternate start and end nodes [OK]

Hint: Reorder means alternate nodes from front and back [OK]

Common Mistakes:

• Confusing reorder with sorting
• Thinking reorder means reversing the list
• Assuming reorder removes duplicates

2. Which of the following C code snippets correctly finds the middle node of a singly linked list for reordering?

easy

A. while (fast && fast->next) { fast = fast->next; slow = slow->next; }

B. while (slow && slow->next) { fast = fast->next; slow = slow->next->next; }

C. while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }

D. while (fast && slow) { slow = slow->next->next; fast = fast->next->next; }

Solution

1. Step 1: Identify the fast and slow pointer technique

   To find the middle node, fast pointer moves two steps, slow pointer moves one step until fast reaches end.

2. Step 2: Check each option for correct pointer movement

   while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } correctly moves fast by two and slow by one. Others have incorrect pointer movements causing errors or wrong middle.

3. Final Answer:

   while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } -> Option C

4. Quick Check:

   Fast moves 2 steps, slow moves 1 step [OK]

Hint: Fast pointer moves twice as fast as slow pointer [OK]

Common Mistakes:

• Swapping fast and slow pointer movements
• Not checking fast->next before fast->next->next
• Using slow pointer to move two steps

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

medium

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

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

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

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

Solution

1. Step 1: Identify the reorder pattern on the list

   The reorder pattern takes first node, last node, second node, second last node, and so on.

2. Step 2: Apply pattern to given list

   Start with 1, then 5, then 2, then 4, then 3. So reordered list is 1 -> 5 -> 2 -> 4 -> 3 -> NULL.

3. Final Answer:

   1 -> 5 -> 2 -> 4 -> 3 -> NULL -> Option D

4. Quick Check:

   Alternate front and back nodes [OK]

Hint: Alternate nodes from start and end [OK]

Common Mistakes:

• Reversing the entire list instead
• Keeping original order unchanged
• Skipping nodes or mixing order

4. Consider this buggy C code snippet for reordering a linked list. What is the main error?

void reorderList(Node* head) {
  Node *slow = head, *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next;
  }
  // further code omitted
}

medium

A. Fast pointer moves only one step instead of two

B. Slow pointer moves two steps instead of one

C. Missing check for head being NULL

D. Using wrong variable names for pointers

Solution

1. Step 1: Analyze pointer movements in the loop

   Fast pointer should move two steps to find middle, but here it moves only one step.

2. Step 2: Identify impact of incorrect fast pointer movement

   This causes slow pointer to not reach the true middle, breaking reorder logic.

3. Final Answer:

   Fast pointer moves only one step instead of two -> Option A

4. Quick Check:

   Fast must move 2 steps, not 1 [OK]

Hint: Fast pointer moves twice as fast as slow [OK]

Common Mistakes:

• Not moving fast pointer two steps
• Ignoring NULL checks
• Confusing slow and fast pointer roles

5. You have a linked list: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> NULL. After reordering, what will be the list? Also, explain why the middle node is chosen as it is.

hard

A. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 40 because it's the node after center

B. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 30 because it's the exact center for even length

C. 10 -> 50 -> 20 -> 40 -> 30 -> 60 -> NULL; middle is 30 because it's the exact center

D. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 20 because it's the first half's end

Solution

1. Step 1: Find the middle node for even length list

   For 6 nodes, middle is node 3 (value 30) because slow pointer stops at exact center when fast moves two steps.

2. Step 2: Apply reorder pattern

   Reorder alternates nodes from start and end: 10, 60, 20, 50, 30, 40.

3. Final Answer:

   10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 30 because it's the exact center for even length -> Option B

4. Quick Check:

   Middle at center, reorder alternates front and back [OK]

Hint: Middle is center node; reorder alternates front and back [OK]

Common Mistakes:

• Choosing wrong middle for even length
• Mixing reorder order
• Confusing node positions