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

↓

Done

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

Execution Sample

DSA Go

func reorderList(head *ListNode) {
 if head == nil || head.Next == nil { return }
 mid := findMiddle(head)
 second := reverseList(mid.Next)
 mid.Next = nil
 mergeLists(head, second)
}

Reorders a linked list by splitting, reversing 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	Middle node found at 3
3	Split list into two halves	First half: 1->2->3->null Second half: 4->5->null	mid.Next set to nil	1 -> 2 -> 3 -> null and 4 -> 5 -> null
4	Reverse second half	4->5->null	4.Next = nil, 5.Next = 4	Second half reversed: 5 -> 4 -> null
5	Merge two 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=nil	Merged list: 1 -> 5 -> 2 -> 4 -> 3 -> null
6	Done	1->5->2->4->3->null	No pointer changes	Final reordered list: 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	nil	points to 3	points to 3	points to 3	points to 3	points to 3
second	nil	nil	points to 4	points to 5	points to 5	points to 5
list size	5 nodes	5 nodes	3 and 2 nodes	3 and 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 nil?

Splitting at mid and setting mid.Next to nil breaks the list into two separate halves, so we can reverse the second half independently without affecting the first half. 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 the merge step alternate nodes from both halves?

During merge, we link one node from the first half, then one from the reversed second half, repeating until all nodes are merged. Pointer changes in step 5 show this clearly.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, which node is identified as the middle?

A Node 3

B Node 2

C Node 4

D Node 5

💡 Hint

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

At which step does the second half get reversed?

A Step 5

B Step 3

C Step 4

D Step 6

💡 Hint

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

If we did not set mid.Next to nil at step 3, what would happen during merge?

A The list would merge correctly anyway

B The merge would create a cycle or incorrect links

C The second half would not reverse properly

D The first half would be lost

💡 Hint

Refer to pointer changes at step 3 and how splitting affects merging in step 5.

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 nodes alternately from first and reversed second half.
Result: nodes reordered as first, last, second, second last, etc.

Full Transcript

This visualization shows how to reorder a linked list by first finding the middle node, splitting the list into two halves, reversing the second half, and then merging the two halves by alternating nodes. The execution table tracks each step with pointer changes and the visual state of the list. Key moments clarify why splitting and reversing are necessary. The quiz tests understanding of middle node identification, reversal step, and the importance of splitting before merging.

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

Solution

1. Step 1: Understand the problem statement

   The problem asks to reorder the list so that nodes come alternately from the start and the end, like L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 and so on.

2. Step 2: Differentiate from other operations

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

3. Final Answer:

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

4. Quick Check:

   Reorder = alternate start/end nodes [OK]

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

Common Mistakes:

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

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

easy

A. class ListNode { int val; ListNode next; }

B. type ListNode struct { Val int; Next *ListNode }

C. struct ListNode { int Val; ListNode* Next; }

D. type ListNode struct { Value int; NextNode *ListNode }

Solution

1. Step 1: Identify Go struct syntax

   In Go, structs are declared with the keyword type, fields have names and types separated by spaces, and pointers use *.

2. Step 2: Match correct field names and types

   type ListNode struct { Val int; Next *ListNode } uses Val int and Next *ListNode, which is the standard for singly linked list nodes in Go.

3. Final Answer:

   type ListNode struct { Val int; Next *ListNode } -> Option B

4. Quick Check:

   Go struct with pointer field = type ListNode struct { Val int; Next *ListNode } [OK]

Hint: Remember Go struct fields: name type; pointer uses * [OK]

Common Mistakes:

• Using C/C++ or Java syntax in Go
• Missing pointer * for next node
• Incorrect field names or types

3. Given the linked list 1 -> 2 -> 3 -> 4 -> 5 -> null, what is the reordered 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 the first node, then the last node, then second node, then second last node, and so on.

2. Step 2: Apply pattern to given list

   Start: 1, end: 5, then 2, then 4, then 3 in the middle. So the reordered list is 1 -> 5 -> 2 -> 4 -> 3 -> null.

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 the entire list instead
• Keeping original order unchanged
• Mixing node order incorrectly

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

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil { return }
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    second := slow.Next
    slow.Next = nil
    var prev *ListNode
    for second != nil {
        next := second.Next
        second.Next = prev
        prev = second
        second = next
    }
    first, second = head, prev
    for second != nil {
        tmp1 := first.Next
        tmp2 := second.Next
        first.Next = second
        second.Next = tmp1
        first = tmp1
        second = tmp2
    }
}

What is the bug in this code?

medium

A. The function does not handle empty or single-node lists

B. The middle node is not correctly found; slow pointer should start at head.Next

C. The loop to reverse the second half does not update the prev pointer correctly

D. The reversed second half is not properly linked back to the first half

Solution

1. Step 1: Analyze the reversal and merging steps

   The code correctly finds the middle, reverses the second half, and then merges nodes alternately.

2. Step 2: Identify the bug in linking halves

   After merging, the last node of the reordered list may still point to old nodes if not handled carefully. The code misses ensuring the last node's Next is nil, causing potential cycle or dangling links.

3. Final Answer:

   The reversed second half is not properly linked back to the first half -> Option D

4. Quick Check:

   Linking halves correctly is key [OK]

Hint: Check if last node's Next is set to nil after merge [OK]

Common Mistakes:

• Not breaking the list at middle properly
• Forgetting to set slow.Next = nil
• Incorrect pointer updates in merge loop

5. You have a linked list with nodes containing values 1 -> 2 -> 3 -> null. After reordering, what will be the list if you apply the reorder linked list algorithm twice in a row?

hard

A. 1 -> 3 -> 2 -> null (same as after first reorder)

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

C. 1 -> 2 -> 3 -> null (original list)

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

Solution

1. Step 1: Apply reorder once

   First reorder transforms 1->2->3 into 1->3->2.

2. Step 2: Apply reorder again on the new list

   Reordering 1->3->2 again returns the original order 1->2->3 because the reorder pattern is symmetric and reverses itself on second application.

3. Final Answer:

   1 -> 2 -> 3 -> null (original list) -> Option C

4. Quick Check:

   Reorder twice returns original list [OK]

Hint: Reordering twice restores original order [OK]

Common Mistakes:

• Assuming reorder twice keeps the first reorder result
• Not recognizing reorder symmetry
• Confusing reorder with reverse