86. Partition List - Explanation
Description
Rearrange the nodes so that every value strictly less than x appears before every value greater than or equal to x. Preserve the original relative order within each of these two groups, and return the new head. Values equal to x belong to the second group. Arrays in examples and test inputs show node values from head to tail; [] represents an empty list.
Example 1:
Input: head = [3,1,4,2,3,0]
x = 3
Output: [1,2,0,3,4,3]Explanation: Values less than 3 are 1, 2, and 0 in that order. The remaining values are 3, 4, and 3 in their original order. Join these groups to obtain 1 -> 2 -> 0 -> 3 -> 4 -> 3.
Example 2:
Input: head = [0,-2,3,-1]
x = 0
Output: [-2,-1,0,3]Explanation: The values below 0 are -2 and -1. Place them before 0 and 3, preserving the order within both groups.
Example 3:
Input: head = []
x = 7
Output: []Explanation: There are no nodes to partition, so the result is an empty list.
Constraints:
- The list contains between
0and200nodes. -100 <= Node.val <= 100-200 <= x <= 200
Topics
Prerequisites
Before attempting this problem, you should be comfortable with:
- Linked Lists - Understanding node structure, traversal, and pointer manipulation
- Two Pointers - Building and maintaining separate lists for partitioning
- Dummy Nodes - Using sentinel nodes to simplify edge case handling when building linked lists
1. Brute Force
Intuition
We need to partition the linked list so that all nodes with values less than x come before nodes with values greater than or equal to x, while preserving the original relative order within each group.
The brute force approach extracts all values into two separate lists based on the partition condition, then writes them back to the original nodes. This simplifies the logic but requires extra space proportional to the list size.
Algorithm
- Create two arrays: one for values less than
x, another for values greater than or equal tox. - Traverse the linked list once, appending each value to the appropriate array.
- Traverse the linked list again, overwriting node values in order: first all values from the "less" array, then all values from the "greater" array.
- Return the
headof the modified list.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
if not head:
return None
less, greater = [], []
cur = head
while cur:
if cur.val < x:
less.append(cur.val)
else:
greater.append(cur.val)
cur = cur.next
cur = head
for val in less:
cur.val = val
cur = cur.next
for val in greater:
cur.val = val
cur = cur.next
return headTime & Space Complexity
- Time complexity:
- Space complexity:
2. Two Pointers
Intuition
Instead of storing values in arrays, we can build two separate linked lists as we traverse: one for nodes less than x, one for nodes greater than or equal to x. Using dummy head nodes simplifies edge case handling.
At the end, we connect the tail of the "less" list to the head of the "greater" list, and terminate the "greater" list to avoid cycles. This achieves O(1) extra space by reusing the original nodes.
Algorithm
- Create two dummy nodes as heads for the "left" (less than
x) and "right" (greater or equal) lists. - Maintain tail pointers for both lists.
- Traverse the original list:
- If the current node's value is less than
x, append it to the left list. - Otherwise, append it to the right list.
- If the current node's value is less than
- Connect the left list's tail to the right list's first real node (skip dummy).
- Set the right list's tail's
nexttonullto terminate the list. - Return the first real node of the left list.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
left, right = ListNode(), ListNode()
ltail, rtail = left, right
while head:
if head.val < x:
ltail.next = head
ltail = ltail.next
else:
rtail.next = head
rtail = rtail.next
head = head.next
ltail.next = right.next
rtail.next = None
return left.nextTime & Space Complexity
- Time complexity:
- Space complexity:
Common Pitfalls
Forgetting to Terminate the Right List
After connecting the left list to the right list, you must set rtail.next = null. Without this, the last node of the right list may still point to a node in the left list from the original structure, creating a cycle and causing infinite loops.
Using Strict Greater Than Instead of Greater or Equal
The partition condition requires nodes with values less than x to come first, and nodes greater than or equal to x to come second. Using > instead of >= for the right partition will incorrectly place nodes equal to x in the left partition.
Not Using Dummy Nodes
Trying to handle the head of each partition manually without dummy nodes leads to complex edge case handling. Using dummy nodes (left and right) as placeholders simplifies the code and eliminates null checks when the first node is encountered for each partition.
Sign in to join the discussion