LeetCode 143: Reorder List — Step-by-Step Visual Trace

Medium — Linked List | Two Pointers | Recursion

The Problem

Given the head of a singly linked list, reorder it by alternating nodes from the beginning and end of the list in-place.

Approach

The algorithm uses a three-step approach: first find the middle of the list using slow/fast pointers, then reverse the second half of the list, and finally merge the two halves by alternating nodes from each half.

Time: O(n) · Space: O(1)

Code

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

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

        # Reverse the second half of the list
        prev, current = None, slow.next
        slow.next = None
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        # Merge the two halves alternately
        p1, p2 = head, prev
        while p2:
            next_p1, next_p2 = p1.next, p2.next
            p1.next = p2
            p2.next = next_p1
            p1, p2 = next_p1, next_p2

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments