京公网安备11010502063487号给定一个链表和一个值 x，把链表重新排列，使所有小于 x 的结点都排在大于或等于 x 的结点之前，并且保持每一部分里结点原来的相对顺序（稳定）。做法是拆成两条链：遍历原链表，小于 x 的接到 small 链的末尾，其余的接到 large 链的末尾，最后把 small 接上 large。用两个哑结点让"链是否为空"不需要特判。这道题有一个隐蔽的坑：大链的最后一个结点在原链表里可能还指向别的结点，如果不把它的 next 断开，拼起来的链表里会有环。本文用真实运行展示这个环，给出五种语言的实现，并把两条链的生长做成分步演示。
完整题目见官方页面（链接在文末）。链表在测试里用整数数组表示。基准解在数组上做两次稳定的筛选：先取所有小于 x 的，再取所有大于等于 x 的，然后拼接，与指针拆链是两种独立的写法。一共 12 组用例，覆盖：官方两个示例、空链表、单个结点、全部小于 x、全部大于等于 x、x 等于某些结点的值、含负数：
输入 [[1,4,3,2,5,2],3] 输出 [1,2,2,4,3,5] 输入 [[2,1],2] 输出 [1,2] 输入 [[],1] 输出 [] 输入 [[1],0] 输出 [1] 输入 [[1],2] 输出 [1] 输入 [[3,3,3],3] 输出 [3,3,3]
原链表里的结点是原样复用的，每个结点的 next 还指着它在原链表里的下一个结点。遍历时，大链的尾结点是原链表里最后一个大于等于 x 的结点，它的 next 可能指向一个已经被接到小链里的结点。如果不把 large.next 置空，最后拼出来的链表末尾会回到前面，形成环。下面是没有断开的写法的真实结果，我最多让它遍历 40 步，走了 40 步还没到尽头就判定为有环：
# 没有断开大链尾结点的写法（遍历时最多走 40 步） [1, 4, 3, 2, 5, 2], x=3: 没断开 -> [1, 2, 2, 4, 3, 5, 2, 4, 3, 5, 2, 4, 3, 5, 2, 4, 3, 5, 2, 4, 3, 5, 2, 4, 3, 5, 2, 4, 3, 5, 2, 4, 3, 5, 2, 4, 3, 5, 2, 4]…（走了 40 步还没到尽头：链表里有环） solve -> [1, 2, 2, 4, 3, 5] [2, 1], x=2: 没断开 -> [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]…（走了 40 步还没到尽头：链表里有环） solve -> [1, 2] [1, 2, 3], x=5: 没断开 -> [1, 2, 3] solve -> [1, 2, 3] [5, 4, 3], x=1: 没断开 -> [5, 4, 3] solve -> [5, 4, 3] [1, 4, 3, 2, 5, 2], x=9: 没断开 -> [1, 4, 3, 2, 5, 2] solve -> [1, 4, 3, 2, 5, 2]
官方示例 [1, 4, 3, 2, 5, 2]（x = 3）：大链是 4 → 3 → 5，5 在原链表里后面还有一个 2（在小链里），没断开时 5 的 next 仍然指向 2，遍历得到 1, 2, 2, 4, 3, 5, 2, 4, 3, 5, ... 无限循环；[2, 1]（x = 2）同样出现环。而 [1, 2, 3]（x = 5，全部小于 x）、[5, 4, 3]（x = 1，全部大于等于 x）、[1, 4, 3, 2, 5, 2]（x = 9）里，大链要么为空，要么大链的尾结点本来就是原链表的最后一个结点（它的 next 本来就是空），所以不出问题。这个错误只在"大链尾结点后面在原链表里还有小结点"时才暴露。
smallDummy、largeDummy 是两条链的哑头，small、large 是两条链当前的尾指针。遍历原链表的每个结点：值小于 x 接到 small 后面，否则接到 large 后面；这里没有新建结点，只是把原来的结点串起来。遍历结束后先把 large.next 置空，再把 small.next 指向大链的第一个结点（largeDummy.next），返回 smallDummy.next。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；这个做法稳定，也只需要 O(1) 的额外空间（只有两个哑结点）。
Python · 解法代码class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def partition_list(head, x): small_dummy, large_dummy = ListNode(), ListNode() # 两条链：小于 x 的、大于等于 x 的 small, large = small_dummy, large_dummy while head: if head.val < x: small.next = head # 依次接到各自的链尾，保持原来的相对顺序 small = small.next else: large.next = head large = large.next head = head.next large.next = None # 必须把大链的尾断开，否则可能残留指回小链的旧指针形成环 small.next = large_dummy.next # 小链接上大链 return small_dummy.next
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,4,3,2,5,2],3] → [1,2,2,4,3,5] [[2,1],2] → [1,2] [[],1] → [] [[1],0] → [1] [[1],2] → [1] [[3,3,3],3] → [3,3,3]
Java · 解法代码class ListNode { int val; ListNode next; ListNode(int v) { val = v; } } class Solution { public ListNode partition(ListNode head, int x) { ListNode smallDummy = new ListNode(0), largeDummy = new ListNode(0); // 两条链：小于 x 的、大于等于 x 的 ListNode small = smallDummy, large = largeDummy; while (head != null) { if (head.val < x) { small.next = head; small = small.next; } // 依次接到各自的链尾，保持原来的相对顺序 else { large.next = head; large = large.next; } head = head.next; } large.next = null; // 必须把大链的尾断开，否则可能残留指回小链的旧指针形成环 small.next = largeDummy.next; // 小链接上大链 return smallDummy.next; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,4,3,2,5,2],3] → [1,2,2,4,3,5] [[2,1],2] → [1,2] [[],1] → [] [[1],0] → [1] [[1],2] → [1] [[3,3,3],3] → [3,3,3]
Go · 解法代码type ListNode struct { Val int Next *ListNode } func partition(head *ListNode, x int) *ListNode { smallDummy, largeDummy := &ListNode{}, &ListNode{} // 两条链：小于 x 的、大于等于 x 的 small, large := smallDummy, largeDummy for head != nil { if head.Val < x { // 依次接到各自的链尾，保持原来的相对顺序 small.Next = head small = small.Next } else { large.Next = head large = large.Next } head = head.Next } large.Next = nil // 必须把大链的尾断开，否则可能残留指回小链的旧指针形成环 small.Next = largeDummy.Next // 小链接上大链 return smallDummy.Next }
$ go build -o bin . && ./bin < cases.jsonl [[1,4,3,2,5,2],3] → [1,2,2,4,3,5] [[2,1],2] → [1,2] [[],1] → [] [[1],0] → [1] [[1],2] → [1] [[3,3,3],3] → [3,3,3]
JavaScript · 解法代码class ListNode { constructor(val = 0, next = null) { this.val = val; this.next = next; } } function partition(head, x) { const smallDummy = new ListNode(), largeDummy = new ListNode(); // 两条链：小于 x 的、大于等于 x 的 let small = smallDummy, large = largeDummy; while (head) { if (head.val < x) { small.next = head; small = small.next; } // 依次接到各自的链尾，保持原来的相对顺序 else { large.next = head; large = large.next; } head = head.next; } large.next = null; // 必须把大链的尾断开，否则可能残留指回小链的旧指针形成环 small.next = largeDummy.next; // 小链接上大链 return smallDummy.next; }
$ node run.js < cases.jsonl [[1,4,3,2,5,2],3] → [1,2,2,4,3,5] [[2,1],2] → [1,2] [[],1] → [] [[1],0] → [1] [[1],2] → [1] [[3,3,3],3] → [3,3,3]
C++ · 解法代码struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} }; class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode smallDummy(0), largeDummy(0); // 两条链：小于 x 的、大于等于 x 的 ListNode *small = &smallDummy, *large = &largeDummy; while (head) { if (head->val < x) { small->next = head; small = small->next; } // 依次接到各自的链尾，保持原来的相对顺序 else { large->next = head; large = large->next; } head = head->next; } large->next = nullptr; // 必须把大链的尾断开，否则可能残留指回小链的旧指针形成环 small->next = largeDummy.next; // 小链接上大链 return smallDummy.next; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,4,3,2,5,2],3] → [1,2,2,4,3,5] [[2,1],2] → [1,2] [[],1] → [] [[1],0] → [1] [[1],2] → [1] [[3,3,3],3] → [3,3,3]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
Python 版本另外和数组两次筛选做了随机对拍：长度 0 到 10、取值 0 到 6，x 取 0 到 7（包括全部小于 x、全部不小于 x 的情形）：
随机对拍 20000 组（长度 0 到 10、取值 0 到 6 的链表，x 取 0 到 7（包含全部小于 x、全部不小于 x 的情形）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。这道题只遍历链表一遍，是线性的，所以没有做规模对比实验。
下面的演示用官方示例 [1, 4, 3, 2, 5, 2]，x = 3。依次处理每个结点：1 和 2、2 小于 3，接到小链；4、3、5 大于等于 3，接到大链。最后小链 1 → 2 → 2 接上大链 4 → 3 → 5，得到 [1, 2, 2, 4, 3, 5]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。