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

fn reorder_list(head: &mut Option<Box<ListNode>>) {
    // 1. Find middle
    // 2. Reverse second half
    // 3. Merge two halves
}

This code reorders a linked list by splitting, reversing, and merging nodes.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Find middle node using slow and fast pointers	1 -> 2 -> 3 -> 4 -> 5 -> null	slow at 3, fast at 5	1 -> 2 -> 3 -> 4 -> 5 -> null
2	Split list into two halves at middle	First half: 1 -> 2 -> 3 -> null Second half: 4 -> 5 -> null	3.next = None	1 -> 2 -> 3 -> null 4 -> 5 -> null
3	Reverse second half	Second half reversed: 5 -> 4 -> null	5.next = 4, 4.next = None	1 -> 2 -> 3 -> null 5 -> 4 -> null
4	Merge two halves alternately	Merging nodes from first and reversed second half	1.next = 5, 5.next = 2, 2.next = 4, 4.next = 3, 3.next = None	1 -> 5 -> 2 -> 4 -> 3 -> null
5	Done	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 1	After Step 2	After Step 3	After Step 4	Final
head	1 -> 2 -> 3 -> 4 -> 5 -> null	1 -> 2 -> 3 -> 4 -> 5 -> null	1 -> 2 -> 3 -> null	1 -> 2 -> 3 -> null	1 -> 5 -> 2 -> 4 -> 3 -> null	1 -> 5 -> 2 -> 4 -> 3 -> null
slow	1	3	3	3	3	3
fast	1	5	5	5	5	5
second_half	4 -> 5 -> null	4 -> 5 -> null	4 -> 5 -> null	5 -> 4 -> null	5 -> 2 -> 4 -> 3 -> null	5 -> 2 -> 4 -> 3 -> null
first_half	1 -> 2 -> 3 -> 4 -> 5 -> null	1 -> 2 -> 3 -> 4 -> 5 -> null	1 -> 2 -> 3 -> null	1 -> 2 -> 3 -> null	1 -> 5 -> 2 -> 4 -> 3 -> null	1 -> 5 -> 2 -> 4 -> 3 -> null

Key Moments - 3 Insights

Why do we split the list at the middle node and set middle.next = None?

Splitting at the middle breaks the list into two separate halves so we can reverse the second half independently. Setting middle.next = None stops the first half from linking to the second half, as shown in step 2 of the 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. This is necessary to achieve the reorder pattern, as shown in step 3 and 4 of the execution_table.

How does the merging step alternate nodes from both halves?

During merging, we take one node from the first half, then one from the reversed second half, and link them alternately. Pointer changes in step 4 show how next pointers are updated to weave the two halves together.

Visual Quiz - 3 Questions

Look at the execution_table at step 1, where is the slow pointer located?

A At node 2

B At node 4

C At node 3

D At node 5

💡 Hint

Check the 'Pointer Changes' column in step 1 of execution_table

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

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for 'Reverse second half' in the 'Operation' column

If the list had only 4 nodes, how would the 'Nodes in List' look after splitting at step 2?

A First half: 1 -> 2 -> null, Second half: 3 -> 4 -> null

B First half: 1 -> 2 -> 3 -> null, Second half: 4 -> null

C First half: 1 -> null, Second half: 2 -> 3 -> 4 -> null

D First half: 1 -> 2 -> 3 -> 4 -> null, Second half: null

💡 Hint

Splitting is done at the middle node, which is node 2 for 4 nodes

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 L0 → Ln → L1 → Ln-1 → L2 → ...

Full Transcript

The reorder linked list algorithm works by first finding the middle node of the list using two pointers moving at different speeds. Then, the list is split into two halves by breaking the link at the middle. The second half is reversed to prepare for merging. Finally, the two halves are merged by alternating nodes from each half, creating the reordered list. This process is shown step-by-step in the execution table, with pointer changes and the visual state of the list after each operation. Key moments clarify why splitting and reversing are necessary, and how merging alternates nodes. The visual quiz tests understanding of pointer positions and list states at each step.

Practice

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

easy

A. Sort the linked list in ascending order

B. Reverse the entire linked list

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

D. Remove duplicate nodes from the list

Solution

1. Step 1: Understand the reorder pattern

   The reorder linked list problem requires rearranging nodes so 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 both ends alternatively.

3. Final Answer:

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

4. Quick Check:

   Reorder = alternate start and end nodes [OK]

Hint: Remember: reorder mixes front and back nodes alternately [OK]

Common Mistakes:

• Confusing reorder with sorting
• Thinking reorder means full reversal
• Assuming duplicates are removed

2. Which Rust syntax correctly defines a singly linked list node struct for Reorder Linked List?

easy

A. struct Node { val: i32, next: Option }

B. struct Node { val: i32, next: &Node }

C. struct Node { val: i32, next: Box<Node> }

D. struct Node { val: i32, next: Option<Node> }

Solution

1. Step 1: Understand Rust ownership for linked lists

   Rust requires using Option for the next pointer to allow nullable and heap allocation.

2. Step 2: Check each option

   struct Node { val: i32, next: Option } uses Option which is correct. struct Node { val: i32, next: &Node } uses a reference which is invalid for ownership. struct Node { val: i32, next: Box<Node> } misses Option so no null. struct Node { val: i32, next: Option<Node> } uses Option<Node> which is invalid because Node is not sized.

3. Final Answer:

   struct Node { val: i32, next: Option } -> Option A

4. Quick Check:

   Rust linked list node = Option [OK]

Hint: Use Option for nullable next pointer in Rust [OK]

Common Mistakes:

• Using references instead of Box for next
• Omitting Option causing compile errors
• Using non-boxed Node causing size errors

3. Given the linked list 1 -> 2 -> 3 -> 4 -> null, what is the reordered list after applying the reorder algorithm?

medium

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

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

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

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

Solution

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

   Start with first node (1), then last node (4), then second node (2), then second last node (3).

2. Step 2: Write the reordered list

   The reordered list is 1 -> 4 -> 2 -> 3 -> null.

3. Final Answer:

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

4. Quick Check:

   Reorder 1-2-3-4 = 1-4-2-3 [OK]

Hint: Alternate nodes from front and back to reorder [OK]

Common Mistakes:

• Reversing entire list instead of alternating
• Keeping original order unchanged
• Swapping adjacent nodes incorrectly

4. Consider this Rust function snippet for reordering a linked list:

fn reorder_list(head: &mut Option) {
    let mut slow = head.as_ref();
    let mut fast = head.as_ref();
    while fast.is_some() && fast.unwrap().next.is_some() {
        slow = slow.unwrap().next.as_ref();
        fast = fast.unwrap().next.as_ref().unwrap().next.as_ref();
    }
}

What is the main issue in this code?

medium

A. The loop condition is incorrect and causes infinite loop

B. Using as_ref() causes immutable borrow, preventing mutation later

C. The unwrap calls will panic if list is empty

D. The slow pointer moves too fast skipping nodes

Solution

1. Step 1: Analyze use of as_ref()

   Using as_ref() creates an immutable reference, so slow and fast cannot be used to mutate the list later.

2. Step 2: Understand mutation needs in reorder

   Reordering requires mutable access to split and merge nodes, so immutable borrows block this.

3. Final Answer:

   Using as_ref() causes immutable borrow, preventing mutation later -> Option B

4. Quick Check:

   Immutable borrow blocks mutation in reorder [OK]

Hint: Use mutable references, not as_ref(), to modify list [OK]

Common Mistakes:

• Ignoring borrow rules causing compile errors
• Assuming unwrap always safe without checks
• Misunderstanding pointer movement speed

5. You have a linked list 1 -> 2 -> 3 -> 4 -> 5 -> null. After splitting the list into two halves, reversing the second half, and merging alternately, what is the final reordered list?

hard

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

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

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

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

Solution

1. Step 1: Split the list into two halves

   For 1->2->3->4->5, the middle is at 3, so first half: 1->2->3, second half: 4->5.

2. Step 2: Reverse the second half

   Reverse 4->5 to get 5->4.

3. Step 3: Merge alternately

   Merge nodes from first and reversed second half: 1->5->2->4->3->null.

4. Final Answer:

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

5. Quick Check:

   Split, reverse second half, merge = 1-5-2-4-3 [OK]

Hint: Split, reverse second half, then merge alternately [OK]

Common Mistakes:

• Not reversing second half before merge
• Merging without alternating nodes
• Incorrect middle node calculation