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
- Build two separate lists: one for nodes below
x, one for nodes at or above it. - Append each node to its list as you traverse, which preserves the relative order automatically.
- Finally, link the tail of the "less" list to the head of the "greater" list.
- 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
<= xfor the first branch: the partition point is strictly less thanx. - 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.