⚡Flashcard Drill➔
NeetCode #332LC-86MediumLinked List
← Back to All Problems

#332 · #86 · Partition List(分隔链表)

📌 Problem Statement & Constraints

Given the head of a linked list and a value x, partition it so that all nodes with values less than x come before nodes with values greater than or equal to x, preserving the original relative order within each part. Constraints: the number of nodes is in [0, 200], -100 <= Node.val <= 100, -200 <= x <= 200.

💡 Core Algorithmic Approaches

  1. Build two separate lists: one for nodes below x, one for nodes at or above it.
  2. Append each node to its list as you traverse, which preserves the relative order automatically.
  3. Finally, link the tail of the "less" list to the head of the "greater" list.
  4. Two dummy heads keep the code free of special cases.

💻 Benchmark Python3 Implementation

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        less = less_tail = ListNode(0)
        greater = greater_tail = ListNode(0)
        cur = head
        while cur:
            if cur.val < x:
                less_tail.next = cur
                less_tail = cur
            else:
                greater_tail.next = cur
                greater_tail = cur
            cur = cur.next
        greater_tail.next = None           # terminate the second list
        less_tail.next = greater.next      # splice
        return less.next

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): the nodes are relinked into two chains.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting greater_tail.next = None: the second list would still point at the remainder of the original list, creating a cycle or duplicate tail.
  • Using <= x for the first branch: the partition point is strictly less than x.
  • Trying to do it in place with swaps: preserving the relative order makes that much harder than the two-list approach.
  • Creating new nodes: the problem expects the existing nodes to be rearranged.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems