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.