Reorder Linked List in DSA Python - Execution Trace

Concept Flow - Reorder Linked List

Start at head

↓

Find middle node using slow & fast pointers

↓

Split list into two halves

↓

Reverse second half

↓

Merge first half and reversed second half alternately

↓

Reordered list complete

The list is split into two halves, the second half is reversed, then both halves are merged alternately to reorder the list.

Execution Sample

DSA Python

def reorderList(head):
    def reverseList(head):
        prev = None
        curr = head
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        return prev

    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None
    second = reverseList(second)
    first = head
    while second:
        tmp1 = first.next
        tmp2 = second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

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	Initialize slow and fast at head	1 -> 2 -> 3 -> 4 -> 5 -> null	slow=head(1), fast=head(1)	1 -> 2 -> 3 -> 4 -> 5 -> null
2	Move slow and fast to find middle	1 -> 2 -> 3 -> 4 -> 5 -> null	slow=2, fast=3	1 -> 2 -> 3 -> 4 -> 5 -> null
3	Move slow and fast again	1 -> 2 -> 3 -> 4 -> 5 -> null	slow=3, fast=5	1 -> 2 -> 3 -> 4 -> 5 -> null
4	fast.next is None, stop loop	1 -> 2 -> 3 -> 4 -> 5 -> null	slow=3, fast=5	1 -> 2 -> 3 -> 4 -> 5 -> null
5	Split list at slow	First half: 1 -> 2 -> 3 -> null Second half: 4 -> 5 -> null	slow.next = None	1 -> 2 -> 3 -> null and 4 -> 5 -> null
6	Reverse second half	4 -> 5 -> null	Reversed second half: 5 -> 4 -> null	5 -> 4 -> null
7	Start merging first and reversed second half	First half: 1 -> 2 -> 3 -> null Second half: 5 -> 4 -> null	first=1, second=5	1 -> 2 -> 3 -> null and 5 -> 4 -> null
8	Merge step 1: link 1 -> 5	Partial merged: 1 -> 5	first.next=5, second.next=2	1 -> 5 -> 2 -> 3 -> null and 4 -> null
9	Merge step 2: link 2 -> 4	Partial merged: 1 -> 5 -> 2 -> 4	first.next=4, second.next=3	1 -> 5 -> 2 -> 4 -> 3 -> null
10	second is None, merging done	Reordered list: 1 -> 5 -> 2 -> 4 -> 3 -> null	first=3, second=None	1 -> 5 -> 2 -> 4 -> 3 -> null

💡 Merging stops when second half pointer becomes None

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	After Step 8	After Step 9	Final
slow	1	2	3	3	3	3	3	3
fast	1	3	5	5	5	5	5	5
first	1	1	1	1	1	2	3	3
second	1	1	1	4	5	4	null	null
List Size	5	5	5	5	5	5	5	5

Key Moments - 3 Insights

Why do we stop moving fast pointer when fast.next is None?

Because fast moves two steps at a time, stopping when fast.next is None ensures slow is at the middle node (see execution_table step 4).

Why do we set slow.next to None after finding middle?

To split the list into two halves, we break the link at slow.next (see execution_table step 5), so the first half ends properly.

How does reversing the second half help in reordering?

Reversing the second half allows us to merge nodes alternately from start and end (see execution_table step 6 and merging steps 8-10).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the position of slow pointer?

A Node 3

B Node 2

C Node 4

D Node 5

💡 Hint

Check the 'Pointer Changes' column at step 3 in execution_table.

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

A Step 4

B Step 6

C Step 5

D Step 7

💡 Hint

Look for the operation mentioning 'Split list' in execution_table.

If the second half was not reversed, how would the merged list look after step 10?

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

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

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

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

💡 Hint

Reversing second half changes order; without reversing, second half remains 4 -> 5.

Concept Snapshot

Reorder Linked List:
- Find middle with slow & fast pointers
- Split list into two halves
- Reverse second half
- Merge halves alternately
- Result: nodes reordered as first, last, second, second last, ...

Full Transcript

To reorder a linked list, we first find the middle node using two pointers moving at different speeds. Then we split the list into two halves by breaking the link at the middle. Next, we reverse the second half to prepare for merging. Finally, we merge nodes from the first half and reversed second half alternately to achieve the reordered list. This process ensures the list is rearranged as first node, last node, second node, second last node, and so on.

Practice

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

easy

A. Remove duplicate nodes from the linked list

B. Sort the linked list in ascending order

C. Reverse the entire linked list

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

Solution

1. Step 1: Understand the problem statement

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

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 D

4. Quick Check:

   Reorder means alternate start/end nodes = A [OK]

Hint: Remember: reorder means alternate front and back nodes [OK]

Common Mistakes:

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

2. Which of the following Python code snippets correctly splits a linked list into two halves for reordering?

easy

A. slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = null

B. slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = null

C. slow, fast = head.next, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = null

D. slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = null

Solution

1. Step 1: Understand slow and fast pointer technique

   Using slow and fast pointers starting at head, fast moves twice as fast to find middle.

2. Step 2: Check code correctness

   slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next second = slow.next slow.next = null correctly initializes both at head and uses while fast and fast.next to move pointers safely.

3. Final Answer:

   Option B code snippet correctly splits the list into two halves -> Option B

4. Quick Check:

   Slow and fast start at head, fast moves twice = B [OK]

Hint: Start slow and fast at head; fast moves twice as fast [OK]

Common Mistakes:

• Starting fast at head.next causes off-by-one errors
• Incorrect while loop conditions causing crashes
• Not breaking the list by setting slow.next = null

3. What is the output linked list after reordering 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

   Reorder means first node, last node, second node, second last node, and so on.

2. Step 2: Apply pattern to given list

   For 1->2->3->4->5, reordered is 1->5->2->4->3.

3. Final Answer:

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

4. Quick Check:

   Alternate front and back nodes = C [OK]

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

Common Mistakes:

• Reversing entire list instead of reordering
• Keeping original order unchanged
• Skipping nodes or mixing order

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

def reorderList(head):
    if not head or not head.next:
        return
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = null
    prev = null
    while second:
        temp = second.next
        second.next = prev
        prev = second
        second = temp
    first, second = head, prev
    while second:
        temp1 = first.next
        temp2 = second.next
        first.next = second
        second.next = temp1
        first = temp1
        second = temp2

medium

A. The function does not return the head after reordering

B. The slow pointer should start at head.next to find middle correctly

C. The while loop merging two halves should check first and second, not just second

D. The code does not handle the case when the list has only one node

Solution

1. Step 1: Analyze function return behavior

   The function modifies the list in place but does not return anything, which is acceptable if list nodes are modified directly.

2. Step 2: Check if returning head is necessary

   Since the list is modified in place, returning head is optional; however, if used in some contexts, returning head is safer.

3. Step 3: Identify actual bug

   All other parts correctly find middle, reverse second half, and merge. The main issue is no return statement if function expected to return head.

4. Final Answer:

   The function does not return the head after reordering -> Option A

5. Quick Check:

   Missing return statement = A [OK]

Hint: Check if function returns the modified list head [OK]

Common Mistakes:

• Starting slow pointer at head.next causing wrong middle
• Merging loop condition incorrect causing infinite loop
• Ignoring single node edge case

5. You have a linked list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null. After applying the reorder linked list algorithm, what will be the final list? Also, explain why the middle node is chosen as it is.

hard

A. 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null; middle chosen to split list evenly

B. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null; no reordering done for even length

C. 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null; middle chosen as the first of the two middle nodes

D. 1 -> 5 -> 2 -> 4 -> 3 -> 6 -> null; middle chosen as the last node

Solution

1. Step 1: Apply reorder pattern to even length list

   For 1->2->3->4->5->6, reordered list is 1->6->2->5->3->4.

2. Step 2: Explain middle node choice

   Using slow and fast pointers, slow stops at the first middle node (3), splitting list into two halves evenly.

3. Final Answer:

   1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null; middle chosen as the first of the two middle nodes -> Option C

4. Quick Check:

   Even length split uses first middle node = D [OK]

Hint: For even length, slow stops at first middle node [OK]

Common Mistakes:

• Choosing second middle node as split point
• Not reordering even length lists
• Mixing node order in final list