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.