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(ListNode* head) {
  if (!head || !head->next) return;
  ListNode* slow = head, *fast = head;
  while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  ListNode* second = slow->next;
  slow->next = nullptr;
  second = reverseList(second);
  mergeLists(head, second);
}

This code reorders a linked list by splitting, reversing the second half, and merging 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 at 3, fast at 5	1 -> 2 -> 3(slow) -> 4 -> 5(fast) -> null
3	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 4 -> 5 -> null
4	Reverse second half	Second half reversed: 5 -> 4 -> null	second points to 5 (new head of reversed half)	1 -> 2 -> 3 -> null 5 -> 4 -> null
5	Merge two halves alternately	Merged list nodes: 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
slow	points to 1	points to 3	points to 3	points to 3	points to 3	points to 3
fast	points to 1	points to 5	points to 5	points to 5	points to 5	points to 5
second	null	null	points to 4	points to 5	points to 5	points to 5
List size	5	5	split into 3 and 2	3 and 2	merged 5	5

Key Moments - 3 Insights

Why do we split the list at the middle node?

Splitting at the middle (Step 3) divides the list into two halves so we can reverse the second half and merge alternately. This is shown in execution_table row 3.

Why do we reverse the second half before merging?

Reversing the second half (Step 4) allows us to merge nodes from the end of the list alternately with nodes from the start, creating the reordered pattern. See execution_table row 4.

How does merging alternate nodes work?

Merging alternates nodes from the first half and reversed second half by rearranging pointers step by step, as shown in execution_table row 5 where nodes are linked 1->5->2->4->3.

Visual Quiz - 3 Questions

Look at the execution table, at which step does the slow pointer reach the middle node?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Check the 'Pointer Changes' column in execution_table row 2 where slow points to 3.

At which step is the second half of the list reversed?

A Step 4

B Step 5

C Step 3

D Step 6

💡 Hint

Look at the 'Operation' column in execution_table row 4 describing reversal.

If the list had 6 nodes instead of 5, how would the split step change?

A Split after node 2, first half 2 nodes, second half 4 nodes

B Split after node 3, first half 3 nodes, second half 3 nodes

C Split after node 4, first half 4 nodes, second half 2 nodes

D No split needed

💡 Hint

Middle is found by slow pointer moving one step and fast pointer two steps; for even nodes, slow stops at node 3.

Concept Snapshot

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

Full Transcript

Reordering a linked list involves splitting it at the middle node, reversing the second half, and then merging the two halves by alternating nodes. We use two pointers, slow and fast, to find the middle. After splitting, the second half is reversed to allow merging nodes from the end and start alternately. Finally, pointers are rearranged to merge the two halves, producing the reordered list. The execution table shows each step with the list state and pointer changes. Key moments clarify why splitting, reversing, and merging are done. The visual quiz tests understanding of these steps.

Practice

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

easy

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

B. Sort the linked list in ascending order

C. Reverse the entire linked list

D. Remove duplicate nodes from the list

Solution

1. Step 1: Understand the problem statement

   The problem asks to reorder the linked list so that nodes are taken alternately from the start and the end, moving towards the center.

2. Step 2: Differentiate from other operations

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

3. Final Answer:

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

4. Quick Check:

   Reorder Linked List = Alternate nodes from start and end [OK]

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

Common Mistakes:

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

2. Which of the following C++ code snippets correctly declares a singly linked list node for the reorder linked list problem?

easy

A. struct ListNode { int val; ListNode* next; ListNode(int x) : val(x) {} };

B. class ListNode { int val; ListNode* next; ListNode(int x) { val = x; next = NULL; } };

C. class ListNode { public: int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };

D. struct ListNode { int val; ListNode* next; ListNode() { val = 0; next = NULL; } };

Solution

1. Step 1: Check access specifiers and constructor

   class ListNode { public: int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; uses class with public members and a constructor initializing val and next properly.

2. Step 2: Identify issues in other options

   A doesn't initialize next. B misses public (members and constructor private by default). C has default constructor but no parameterized one.

3. Final Answer:

   class ListNode with public members and parameterized constructor -> Option C

4. Quick Check:

   Proper class with public and constructor = class ListNode { public: int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; [OK]

Hint: Use public members and constructor initialization list [OK]

Common Mistakes:

• Missing public keyword in class
• Not initializing next pointer
• Using struct without constructor

3. What will be the reordered linked list after applying the reorder algorithm on the list: 1 -> 2 -> 3 -> 4 -> 5 -> null?

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 the reorder pattern

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

2. Step 2: Apply pattern to given list

   Start with 1, then 5, then 2, then 4, then 3 in the middle.

3. Final Answer:

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

4. Quick Check:

   Alternate front and back nodes = 1 -> 5 -> 2 -> 4 -> 3 -> null [OK]

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

Common Mistakes:

• Reversing entire list instead
• Not alternating nodes correctly
• Leaving list unchanged

4. Given the following code snippet for reordering a linked list, what is the main bug causing incorrect output?

void reorderList(ListNode* head) {
  if (!head) return;
  ListNode* slow = head;
  ListNode* fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  ListNode* second = slow;
  ListNode* prev = nullptr;
  while (second) {
    ListNode* tmp = second->next;
    second->next = prev;
    prev = second;
    second = tmp;
  }
  ListNode* first = head;
  second = prev;
  while (second) {
    ListNode* tmp1 = first->next;
    ListNode* tmp2 = second->next;
    first->next = second;
    second->next = tmp1;
    first = tmp1;
    second = tmp2;
  }
}

medium

A. The list is not checked for empty before processing

B. The fast pointer initialization is incorrect

C. The middle node is included in the reversed second half causing cycle

D. The merging loop condition should be while (second->next) not while (second)

Solution

1. Step 1: Analyze the merging loop condition

   The merging loop uses while (second), which processes one extra node causing cycle or incorrect linking.

2. Step 2: Correct loop condition

   Changing it to while (second->next) ensures all nodes from the second half are merged properly without overlap.

3. Final Answer:

   The merging loop condition should be while (second->next) not while (second) -> Option D

4. Quick Check:

   Loop condition must stop before the last overlapping node [OK]

Hint: Use while(second->next) to merge without cycle [OK]

Common Mistakes:

• Using while(second) creates cycle
• Not reversing second half correctly
• Not handling empty list

5. You have a linked list with nodes: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null. After applying the reorder linked list algorithm, what will be the final list?

hard

A. 60 -> 50 -> 40 -> 30 -> 20 -> 10 -> null

B. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> null

C. 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null

D. 10 -> 30 -> 50 -> 60 -> 40 -> 20 -> null

Solution

1. Step 1: Identify the reorder pattern

   The reorder pattern takes nodes alternately from the front and back: first node, last node, second node, second last node, and so on.

2. Step 2: Apply pattern to given list

   Start with 10, then 60, then 20, then 50, then 30, then 40.

3. Final Answer:

   10 -> 60 -> 20 -> 50 -> 30 -> 40 -> null -> Option B

4. Quick Check:

   Alternate front and back nodes = 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> null [OK]

Hint: Alternate nodes from front and back until center [OK]

Common Mistakes:

• Reversing entire list instead
• Not alternating nodes properly
• Leaving list unchanged