LeetCode 86: Partition List (Two Dummy Lists + Stable Merge)
LeetCode 86Linked ListTwo PointersStable PartitionToday we solve LeetCode 86 - Partition List.
Source: https://leetcode.com/problems/partition-list/
English
Problem Summary
Given the head of a linked list and a value x, reorder the list so all nodes with value less than x come before nodes with value greater than or equal to x, while preserving the original relative order inside each group.
Key Insight
Build two chains during one pass: small for nodes < x and large for nodes >= x. Because we append nodes in traversal order, each chain stays stable. Finally connect smallTail.next = largeHead.next.
Brute Force and Limitations
Copying values to an array and rewriting nodes can work, but it is not elegant for linked lists and can easily break stability if handled carelessly.
Optimal Algorithm Steps
1) Create two dummy heads: smallDummy and largeDummy.
2) Traverse the original list node by node.
3) If node.val < x, append to small; otherwise append to large.
4) Terminate large with null to avoid cycles.
5) Stitch: smallTail.next = largeDummy.next; return smallDummy.next.
Complexity Analysis
Time: O(n) (single traversal).
Space: O(1) extra node storage (ignoring dummy pointers).
Common Pitfalls
- Forgetting largeTail.next = null, which may keep old next pointers and create loops.
- Breaking stability by inserting at list front instead of appending.
- Losing next reference before rewiring current node.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode smallDummy = new ListNode(0);
ListNode largeDummy = new ListNode(0);
ListNode small = smallDummy, large = largeDummy;
ListNode cur = head;
while (cur != null) {
if (cur.val < x) {
small.next = cur;
small = small.next;
} else {
large.next = cur;
large = large.next;
}
cur = cur.next;
}
large.next = null;
small.next = largeDummy.next;
return smallDummy.next;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func partition(head *ListNode, x int) *ListNode {
smallDummy := &ListNode{}
largeDummy := &ListNode{}
small, large := smallDummy, largeDummy
for cur := head; cur != nil; cur = cur.Next {
if cur.Val < x {
small.Next = cur
small = small.Next
} else {
large.Next = cur
large = large.Next
}
}
large.Next = nil
small.Next = largeDummy.Next
return smallDummy.Next
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode smallDummy(0), largeDummy(0);
ListNode* small = &smallDummy;
ListNode* large = &largeDummy;
for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
if (cur->val < x) {
small->next = cur;
small = small->next;
} else {
large->next = cur;
large = large->next;
}
}
large->next = nullptr;
small->next = largeDummy.next;
return smallDummy.next;
}
};# 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]:
small_dummy = ListNode(0)
large_dummy = ListNode(0)
small, large = small_dummy, large_dummy
cur = head
while cur:
if cur.val < x:
small.next = cur
small = small.next
else:
large.next = cur
large = large.next
cur = cur.next
large.next = None
small.next = large_dummy.next
return small_dummy.next/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var partition = function(head, x) {
const smallDummy = new ListNode(0);
const largeDummy = new ListNode(0);
let small = smallDummy, large = largeDummy;
for (let cur = head; cur !== null; cur = cur.next) {
if (cur.val < x) {
small.next = cur;
small = small.next;
} else {
large.next = cur;
large = large.next;
}
}
large.next = null;
small.next = largeDummy.next;
return smallDummy.next;
};中文
题目概述
给定链表头结点和整数 x，将链表重排为：所有小于 x 的节点在前，所有大于等于 x 的节点在后，并且两组内部的相对顺序都要保持不变。
核心思路
一次遍历维护两条链：small（< x）和 large（>= x）。按遇到顺序追加节点，因此天然稳定。最后把 small 链尾接到 large 链头即可。
暴力解法与不足
把值拷到数组再回填虽然可行，但不够链表友好，也容易在实现中破坏稳定性。
最优算法步骤
1）创建两个哑节点：smallDummy 与 largeDummy。
2）遍历原链表。
3）若 node.val < x，追加到 small 链；否则追加到 large 链。
4）令 largeTail.next = null，防止旧指针残留导致成环。
5）拼接：smallTail.next = largeDummy.next，返回 smallDummy.next。
复杂度分析
时间复杂度 O(n)；空间复杂度 O(1)（仅额外指针）。
常见陷阱
- 忘记把 large 链尾置空，可能形成环或脏链。
- 头插法会破坏“相对顺序保持不变”的要求。
- 改指针前没保存/管理 next，导致节点丢失。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode smallDummy = new ListNode(0);
ListNode largeDummy = new ListNode(0);
ListNode small = smallDummy, large = largeDummy;
ListNode cur = head;
while (cur != null) {
if (cur.val < x) {
small.next = cur;
small = small.next;
} else {
large.next = cur;
large = large.next;
}
cur = cur.next;
}
large.next = null;
small.next = largeDummy.next;
return smallDummy.next;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func partition(head *ListNode, x int) *ListNode {
smallDummy := &ListNode{}
largeDummy := &ListNode{}
small, large := smallDummy, largeDummy
for cur := head; cur != nil; cur = cur.Next {
if cur.Val < x {
small.Next = cur
small = small.Next
} else {
large.Next = cur
large = large.Next
}
}
large.Next = nil
small.Next = largeDummy.Next
return smallDummy.Next
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode smallDummy(0), largeDummy(0);
ListNode* small = &smallDummy;
ListNode* large = &largeDummy;
for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
if (cur->val < x) {
small->next = cur;
small = small->next;
} else {
large->next = cur;
large = large->next;
}
}
large->next = nullptr;
small->next = largeDummy.next;
return smallDummy.next;
}
};# 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]:
small_dummy = ListNode(0)
large_dummy = ListNode(0)
small, large = small_dummy, large_dummy
cur = head
while cur:
if cur.val < x:
small.next = cur
small = small.next
else:
large.next = cur
large = large.next
cur = cur.next
large.next = None
small.next = large_dummy.next
return small_dummy.next/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var partition = function(head, x) {
const smallDummy = new ListNode(0);
const largeDummy = new ListNode(0);
let small = smallDummy, large = largeDummy;
for (let cur = head; cur !== null; cur = cur.next) {
if (cur.val < x) {
small.next = cur;
small = small.next;
} else {
large.next = cur;
large = large.next;
}
}
large.next = null;
small.next = largeDummy.next;
return smallDummy.next;
};
Comments