💬 Discord
Sign In
NeetCode #319LC-143MediumLinked ListBlind 75NC 150NC 250
← Back to All Problems

#319 · #143 · Reorder List(重排链表)

📌 Problem Statement & Constraints

You are given the head of a singly linked list L0 -> L1 -> ... -> Ln. Reorder it in place to L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> .... You may not modify the values in the nodes. Constraints: the number of nodes is in [1, 5 * 10^4].

💡 Core Algorithmic Approaches

  1. Three steps: find the middle with slow/fast pointers, reverse the second half, then merge the two halves alternately.
  2. Splitting at the middle requires severing the link (slow.next = None) so the halves are independent.
  3. The merge interleaves nodes one at a time; since the second half is reversed, taking one from each half in order produces the required pattern.
  4. All three steps are O(n) with O(1) extra space.

💻 Benchmark Python3 Implementation

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return
        # 1) find the middle (slow ends at the last node of the first half)
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 2) reverse the second half
        prev, cur = None, slow.next
        slow.next = None                # sever the two halves
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        # 3) interleave
        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): three linear passes.
💾 Space Complexity
O(1): the reordering is done by relinking nodes.

⚠️ Interview Pitfalls & Follow-ups

  • Starting fast at head instead of head.next: the middle would be off by one, leaving the halves of unequal length and breaking the interleave.
  • Forgetting slow.next = None: the two halves would still be joined, and the interleave would loop.
  • Building a new list of values: the problem forbids modifying values and expects relinking.
  • Not handling a single-node list: the early return covers it.