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 linked list complete

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

Execution Sample

DSA C#

void ReorderList(ListNode head) {
  if (head == null) return;
  ListNode mid = FindMiddle(head);
  ListNode second = Reverse(mid.next);
  mid.next = null;
  Merge(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	1->2->3->4->5->null	slow at 3, fast at 5	1 -> 2 -> 3(slow) -> 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	4->5->null	5.next = 4, 4.next = null	5 -> 4 -> null
5	Merge halves alternately	First half: 1->2->3->null Second half reversed: 5->4->null	1.next = 5, 5.next = 2, 2.next = 4, 4.next = 3, 3.next = null	1 -> 5 -> 2 -> 4 -> 3 -> null
6	Reordering complete	1->5->2->4->3->null	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	1	1	1	1	1	1
slow (middle)	null	3	3	3	3	3
fast	null	5	5	5	5	5
mid.next	null	4	null	null	null	null
second half start	null	4	4	5	5	5
merged list	null	null	null	null	1->5->2->4->3	1->5->2->4->3

Key Moments - 3 Insights

Why do we set mid.next = null after finding the middle?

Setting mid.next = null splits the list into two separate halves, as shown in step 3 of the execution_table. This prevents the two halves from being connected during reversal and merging.

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 original list alternately with nodes from the start, achieving the reorder pattern.

How does the merge step alternate nodes from both halves?

In step 5, pointers are changed to link one node from the first half, then one from the reversed second half, repeating until all nodes are merged alternately.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, which node does the slow pointer point to?

A Node 2

B Node 3

C Node 4

D Node 5

💡 Hint

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

At which step does the list get split into two halves?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for the operation describing splitting and pointer changes setting mid.next to null.

If we skip reversing the second half, what would be the visual state after merging?

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

B 1 -> 5 -> 2 -> 4 -> 3 -> null

C 1 -> 2 -> 3 -> 4 -> 5 -> null

D 1 -> 3 -> 2 -> 4 -> 5 -> null

💡 Hint

Compare the 'Visual State' at step 5 with and without reversing the second half.

Concept Snapshot

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

Full Transcript

The reorder linked list algorithm starts by finding the middle node using two pointers moving at different speeds. Once the middle is found, the list is split into two halves by setting the middle node's next pointer to null. The second half is then reversed to prepare for merging. Finally, the two halves are merged by alternating nodes from each half, resulting in a reordered list where nodes alternate from the start and end of the original list. This process is shown step-by-step in the execution table, with pointer changes and visual states of the list after each operation.

Practice

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

easy

A. Reverse the entire linked list

B. Sort the linked list in ascending order

C. Rearrange the list so nodes alternate from start and end

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 arranged by alternating from the start and the end of the list.

2. Step 2: Differentiate from other operations

   This is not sorting or reversing the whole list, but a specific pattern: first node, last node, second node, second last node, and so on.

3. Final Answer:

   Rearrange the list so nodes alternate from start and end -> Option C

4. Quick Check:

   Reorder means 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 full reversal
• Ignoring the alternating pattern

2. Which of the following C# code snippets correctly declares a singly linked list node class used in reorder linked list problems?

easy

A. public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } }

B. class Node { int val; Node next; Node(int x) { val = x; next = null; } }

C. public struct ListNode { public int val; public ListNode next; }

D. public class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }

Solution

1. Step 1: Check for public accessibility and constructor

   public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } correctly declares a public class with public fields and a constructor initializing value and next pointer.

2. Step 2: Identify missing public keywords and struct misuse

   Options A and D miss public keywords making fields inaccessible; C uses struct which is not typical for linked list nodes.

3. Final Answer:

   public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } -> Option A

4. Quick Check:

   Public class with constructor and public fields [OK]

Hint: Use public class with constructor and public fields [OK]

Common Mistakes:

• Omitting public keyword for fields
• Using struct instead of class
• Missing constructor initialization

3. Given the linked list: 1 -> 2 -> 3 -> 4 -> 5 -> null, what will be the list after applying the reorder linked list 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 the reorder pattern

   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 remains in the middle.

3. Final Answer:

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

4. Quick Check:

   Alternate front and back nodes [OK]

Hint: Alternate nodes from front and back [OK]

Common Mistakes:

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

4. Consider this C# code snippet for reordering a linked list. What is the bug?

public void ReorderList(ListNode head) {
  if (head == null) return;
  ListNode slow = head, fast = head;
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  ListNode second = ReverseList(slow);
  ListNode first = head;
  while (second != null) {
    ListNode temp1 = first.next;
    ListNode temp2 = second.next;
    first.next = second;
    second.next = temp1;
    first = temp1;
    second = temp2;
  }
}

medium

A. The ReverseList method is missing

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

C. The fast pointer initialization is incorrect

D. The loop condition should be while (second.next != null)

Solution

1. Step 1: Analyze slow pointer position after loop

   After the loop, slow points to the middle node, which is included in the reversed second half.

2. Step 2: Understand consequence of including middle node

   Including the middle node causes the merged list to have a cycle or incorrect links because the middle node is connected twice.

3. Final Answer:

   The middle node is included in the reversed second half causing cycle -> Option B

4. Quick Check:

   Exclude middle node before reversing second half [OK]

Hint: Exclude middle node before reversing second half [OK]

Common Mistakes:

• Not splitting list before reversing second half
• Incorrect loop conditions
• Assuming ReverseList is missing error

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

hard

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

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

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

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

Solution

1. Step 1: Identify the reorder pattern for even length list

   For even nodes, reorder alternates first and last nodes: 10, 60, 20, 50, 30, 40.

2. Step 2: Apply the pattern to given list

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

3. Final Answer:

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

4. Quick Check:

   Alternate front and back nodes for even length [OK]

Hint: Alternate nodes from front and back for even length [OK]

Common Mistakes:

• Reversing entire list instead of reordering
• Not handling even length correctly
• Leaving list unchanged