Reorder Linked List in DSA Python

Mental Model

We rearrange the list so nodes alternate from the start and end towards the center.

Analogy: Imagine lining up people from two ends of a line and making them walk towards the middle, alternating one from the front, then one from the back.

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

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5 -> null

Goal: Rearrange to 1 -> 5 -> 2 -> 4 -> 3 -> null

Step 1: Find middle node using slow and fast pointers

1 -> 2 -> 3 -> 4 -> 5 -> null
           ↑slow, ↑↑fast

Why: We need to split the list into two halves at the middle

Step 2: Split list into two halves: first half 1->2->3, second half 4->5

First half: 1 -> 2 -> 3 -> null
Second half: 4 -> 5 -> null

Why: Separating halves helps us reorder by merging front and reversed back

Step 3: Reverse second half: 4 -> 5 -> null becomes 5 -> 4 -> null

Reversed second half: 5 -> 4 -> null

Why: Reversing back half allows easy alternating merge from front and back

Step 4: Merge first half and reversed second half alternately

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

Why: Alternating nodes from front and back halves achieves the reorder

Result:

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

Annotated Code

DSA Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head: ListNode) -> None:
    if not head or not head.next:
        return

    # Find middle
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Split and reverse second half
    second = slow.next
    slow.next = None
    prev = None
    while second:
        tmp = second.next
        second.next = prev
        prev = second
        second = tmp

    # Merge two halves
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

# Helper to print list
def printList(head: ListNode) -> None:
    curr = head
    res = []
    while curr:
        res.append(str(curr.val))
        curr = curr.next
    print(" -> ".join(res) + " -> null")

# Driver code
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
printList(head)
reorderList(head)
printList(head)

while fast and fast.next:

advance slow and fast pointers to find middle node

second = slow.next slow.next = None

split list into two halves by breaking link at middle

while second: tmp = second.next second.next = prev prev = second second = tmp

reverse second half of the list

while second: tmp1, tmp2 = first.next, second.next first.next = second second.next = tmp1 first, second = tmp1, tmp2

merge nodes from first and reversed second half alternately

Output

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

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

Complexity Analysis

Time: O(n) because we traverse the list multiple times but each traversal is linear

Space: O(1) because we reorder the list in place without extra data structures

vs Alternative: Naive approach might use extra arrays to reorder, costing O(n) space; this approach is more space efficient

Edge Cases

empty list

function returns immediately without changes

DSA Python

if not head or not head.next:
    return

single node list

function returns immediately without changes

DSA Python

if not head or not head.next:
    return

list with two nodes

reordering does not change list as it is already alternating

DSA Python

while fast and fast.next:

When to Use This Pattern

When asked to reorder a linked list alternating from front and back, use the reorder list pattern by splitting, reversing second half, and merging.

Common Mistakes

Mistake: Not breaking the list into two halves before reversing second half
Fix: Set slow.next = None to split the list before reversing

Mistake: Merging without handling the end of one half causing cycles
Fix: Use careful pointer updates and stop merging when second half is exhausted

Summary

Rearranges a linked list so nodes alternate from start and end towards the center.

Use when you need to reorder a list in a specific alternating pattern without extra space.

The key is to find the middle, reverse the second half, then merge alternately.