LeetCode 143: Reorder List Solution in Python Explained

Problem Statement

In LeetCode 143, you’re given the head of a singly linked list L0→L1→…→Ln-1→Ln. Your task is to reorder it in-place to L0→Ln→L1→Ln-1→L2→Ln-2→…. This differs from cycle detection like LeetCode 142: Linked List Cycle II, focusing on restructuring rather than finding loops.

Constraints

• Number of nodes: 1 <= n <= 5 * 10^4
• Node values: -100 <= Node.val <= 100

Example

Let’s see some cases:

Copy codeInput: head = [1,2,3,4]
Output: [1,4,2,3]
Explanation: 
<ul>
<li>Original: 1->2->3->4</li>
<li>Reordered: 1->4->2->3</li>
</ul>

Copy codeInput: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Explanation: 
<ul>
<li>Original: 1->2->3->4->5</li>
<li>Reordered: 1->5->2->4->3</li>
</ul>

Copy codeInput: head = [1]
Output: [1]
Explanation: Single node, no change.

These examples show we’re interleaving the list ends.

Understanding the Problem

How do you solve LeetCode 143: Reorder List in Python? Take head = [1,2,3,4]. We need to reorder it to 1->4->2->3—taking the first node (1), last node (4), second node (2), second-to-last node (3). For [1,2,3,4,5], it becomes 1->5->2->4->3. This isn’t a word break problem like LeetCode 140: Word Break II; it’s about linked list reordering. We’ll use: 1. Three-Step Reversal: O(n) time, O(1) space—our best solution. 2. Using a Stack: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Three-Step Reversal Approach

Explanation

Three-Step Reversal reorders the list in three phases: 1. Find Middle: Use slow and fast pointers to split the list into two halves. 2. Reverse Second Half: Reverse the second half in-place. 3. Merge: Interleave the first half and reversed second half.

This is the best solution due to its O(n) time complexity, O(1) space usage (no extra structures), and efficient in-place manipulation, making it both optimal and elegant.

For [1,2,3,4]:

• Split: 1->2 and 3->4.
• Reverse: 3->4 becomes 4->3.
• Merge: 1->4->2->3.

Step-by-Step Example

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

Example 1: head = [1,2,3,4]

Goal: Reorder to [1,4,2,3].

• Step 1: Find Middle:
• slow = 1, fast = 1.
• slow = 2, fast = 3.
• slow = 3, fast = null, prev = 2.
• Split at 2: 1->2 and 3->4.
• Step 2: Reverse Second Half:
• 3->4 → 4->3.
• Step 3: Merge:
• First: 1->2.
• Second: 4->3.
• Merge: 1->4->2->3.
• Finish: Return head (1).

Example 2: head = [1,2,3,4,5]

Goal: Reorder to [1,5,2,4,3].

• Step 1: Middle at 3 (prev = 2): 1->2->3 and 4->5.
• Step 2: Reverse 4->5 → 5->4.
• Step 3: Merge 1->2->3 and 5->4 → 1->5->2->4->3.
• Finish: Return head (1).

Example 3: head = [1]

Goal: Return [1].

• Step 1: Single node, no split needed.
• Finish: Return head (1).

How the Code Works (Three-Step Reversal) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

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

def reorderList(head: ListNode) -> None:
    # Line 1: Handle null or single node cases
    if not head or not head.next:
        # If head is None or single (e.g., [1]), no reorder needed
        return

    # Line 2: Step 1 - Find middle with slow and fast pointers
    slow = fast = head
    # Both start at head (e.g., 1)
    prev = None
    # Tracks node before middle (e.g., for splitting)
    while fast and fast.next:
        # Move until fast reaches end (e.g., null)
        prev = slow
        # Update prev (e.g., 2 before 3)
        slow = slow.next
        # One step (e.g., 1->2)
        fast = fast.next.next
        # Two steps (e.g., 1->3)
    # After: slow at middle (e.g., 3), prev at 2

    # Line 3: Split into two lists
    second = slow
    # Second half starts at middle (e.g., 3)
    prev.next = None
    # Break link (e.g., 2->null), first half: 1->2

    # Line 4: Step 2 - Reverse second half
    prev = None
    # Reset prev for reversal
    curr = second
    # Start at second half (e.g., 3)
    while curr:
        # Reverse links (e.g., 3->4 to 4->3)
        next_node = curr.next
        # Save next (e.g., 4)
        curr.next = prev
        # Reverse link (e.g., 3->null)
        prev = curr
        # Move prev (e.g., 3)
        curr = next_node
        # Move curr (e.g., 4)
    second = prev
    # Second now reversed (e.g., 4->3)

    # Line 5: Step 3 - Merge first and second halves
    first = head
    # First half (e.g., 1->2)
    while second:
        # While second half remains (e.g., 4->3)
        temp1 = first.next
        # Save first’s next (e.g., 2)
        temp2 = second.next
        # Save second’s next (e.g., 3)
        first.next = second
        # Link first to second (e.g., 1->4)
        if temp1:
            # If first half continues
            second.next = temp1
            # Link second to first’s next (e.g., 4->2)
        first = temp1
        # Move first (e.g., 2)
        second = temp2
        # Move second (e.g., 3)
    # Result: 1->4->2->3

This detailed breakdown clarifies how the three-step reversal efficiently reorders the list.

Alternative: Using a Stack Approach

Explanation

Using a Stack stores all nodes in a stack, then interleaves by popping from the end and linking with the front. It’s a practical alternative, intuitive with O(n) time, but uses O(n) space, less optimal than reversal for space constraints.

For [1,2,3,4]:

• Stack: [1,2,3,4].
• Link: 1->4->2->3.

Step-by-Step Example (Alternative)

For [1,2,3,4]:

• Step 1: stack = [1,2,3,4].
• Step 2:
• 1->4, pop 4.
• 4->2, pop 3 (skip).
• 2->3, done.
• Finish: 1->4->2->3.

How the Code Works (Stack)

Copy codedef reorderListStack(head: ListNode) -> None:
    if not head or not head.next:
        return
    stack = []
    curr = head
    while curr:
        stack.append(curr)
        curr = curr.next
    left = head
    right = stack[-1]
    for i in range(len(stack) // 2):
        temp = left.next
        left.next = right
        right.next = temp
        left = temp
        stack.pop()
        right = stack[-1]
    left.next = None

Complexity

• Three-Step Reversal:
• Time: O(n) – three linear passes.
• Space: O(1) – constant space.
• Using a Stack:
• Time: O(n) – build stack and merge.
• Space: O(n) – stack storage.

Efficiency Notes

Three-Step Reversal is the best solution with O(n) time and O(1) space, meeting optimal constraints elegantly—Using a Stack matches time complexity but uses O(n) space, making it simpler but less space-efficient.

Key Insights

• Reversal: In-place efficiency.
• Stack: Explicit end access.
• Interleaving: Alternates halves.

Additional Example

For head = [1,2,3]:

• Goal: [1,3,2].
• Reversal: Split 1->2, 3, reverse 3, merge 1->3->2.

Edge Cases

• Single Node: [1] → [1].
• Two Nodes: [1,2] → [1,2].
• Odd Length: [1,2,3] → [1,3,2].

Both solutions handle these well.

Final Thoughts

LeetCode 143: Reorder List in Python is a clever linked list challenge. The Three-Step Reversal solution excels with its efficiency and minimalism, while Using a Stack offers an intuitive approach. Want more? Try LeetCode 141: Linked List Cycle for cycle basics or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 143 on LeetCode with [1,2,3,4], aiming for [1,4,2,3]—test your skills now!