C++实现单链表按k值重新排序的方法

前言

「按 k 值重新排序」这个说法本身有歧义。常见的有三种理解：一是以 k 为分界，把小于 k 的节点排在前面、其余排在后面，保持各自相对顺序；二是把链表旋转 k 位；三是每 k 个节点为一组做反转。「按 k 值」强调的是节点的值，因此本文取第一种，也就是按值划分（partition）。如果你的题目其实是后两种，本文末尾的对照表会指出差异，避免套错算法。

很多人的第一反应是「把节点的值排序」或者「交换节点里的值」。对数组可以，对链表则要看题目要求：若题目允许只改值，直接排序值当然可行；但链表题通常要求调整节点连接关系，且往往要求稳定——相同类别的节点保持原有先后。只交换值无法保证稳定性，也无法处理节点里还有其他成员的情况。

本文用 C++17 实现一个原地拆分再拼接的版本：时间复杂度O(n)，额外空间O(1)，只改指针，不新建节点，稳定。代码逐行推演，重点讲清楚拆链时容易丢节点、成环、断链的三个位置。

一、先确认「按 k 重排」到底是哪一种

本文只讲第一行。判断方法很简单：如果题目说「比 k 小的放前面」，就是划分；如果说「向右移动 k 个位置」，是旋转；如果说「每 k 个翻转」，是分组反转。三者的循环结构完全不同，不要混用。

划分问题还有一个隐含条件：k 不一定出现在链表里。例如链表1 -> 4 -> 3 -> 2 -> 5，k 取 3，结果应当是1 -> 2 -> 4 -> 3 -> 5。注意 3 本身归入「大于等于 k」的一侧，所以比较用的是严格小于。若题目要求「小于等于 k 在前」，只需把<改成<=，但一定要先读清题意。

二、为什么用「双虚拟头」而不是原地交换

链表的节点在内存里不连续，无法像数组那样用下标随机访问。要在原地把节点分成两组，最自然的做法是准备两个「桶」，遍历原链表，把每个节点摘下来挂到对应的桶尾。这里的桶用两个虚拟头节点（dummy node）表示，它们不存储有效数据，只负责让「第一个节点」和「后续节点」的插入逻辑一致。

虚拟头的价值在于消除边界判断。没有它，插入第一个节点时要单独写if (head == nullptr)；有了它，所有插入都是「尾指针的 next 指向新节点，再更新尾指针」，不需要特判。

拆分时必须先保存cur->next再修改cur->next。这是整个算法最容易出错的一行：一旦把cur->next指向桶尾，原来的后继就丢了，循环无法继续。正确顺序是：

next = cur->next; // 先记住原来的后继
把 cur 挂到某个桶尾; // 此时可以安全修改 cur->next
cur = next; // 沿原链前进

拼接阶段则要把两个桶接起来，并且把第二个桶的尾节点的 next 置空。否则尾节点可能还指着原链表中的某个节点，形成环。成环的链表在打印或析构时会无限循环，是链表题最常见的崩溃原因。

三、完整实现

下面的代码包含节点定义、建表、划分、打印和释放。划分函数返回新的头指针，调用者负责释放。

// 适用于 C++17
#include <iostream>
#include <vector>

struct Node {
int val;
Node* next;
explicit Node(int v) : val(v), next(nullptr) {}
};

// 以 k 为界稳定划分：小于 k 的在前，其余在后
Node* partitionByK(Node* head, int k) {
Node lessDummy(0);
Node geDummy(0);
Node* lessTail = &lessDummy;
Node* geTail = &geDummy;

Node* cur = head;
while (cur != nullptr) {
Node* next = cur->next; // 先保存后继
if (cur->val < k) {
lessTail->next = cur;
lessTail = cur;
} else {
geTail->next = cur;
geTail = cur;
}
cur = next;
}

lessTail->next = geDummy.next; // 两段相接
geTail->next = nullptr; // 断开原来的尾，防止成环
return lessDummy.next;
}

Node* build(const std::vector<int>& values) {
Node dummy(0);
Node* tail = &dummy;
for (int v : values) {
tail->next = new Node(v);
tail = tail->next;
}
return dummy.next;
}

void print(const Node* head) {
for (const Node* p = head; p != nullptr; p = p->next) {
std::cout << p->val;
if (p->next != nullptr) std::cout << " -> ";
}
std::cout << '\n';
}

void destroy(Node* head) {
while (head != nullptr) {
Node* next = head->next;
delete head;
head = next;
}
}

int main() {
Node* head = build({1, 4, 3, 2, 5});
print(head);
head = partitionByK(head, 3);
print(head);
destroy(head);
return 0;
}

按标准语义推演，输入1 4 3 2 5、k 为 3 时：小于 3 的节点依次是 1、2，其余是 4、3、5，拼接后应当是1 -> 2 -> 4 -> 3 -> 5。稳定性体现在 4 仍然排在 3 前面，5 仍在最后。

如果不想手动delete，可以把节点定义改成std::unique_ptr<Node>，但拆分时需要release()转移所有权，代码反而更绕。对链表这种节点数固定、生命周期统一的结构，用一个destroy函数配合 RAII 包装类（析构时调用destroy）是更实际的折中。

四、边界与变体

空链表：head == nullptr，循环不执行，lessTail仍指向lessDummy，lessDummy.next为nullptr，geTail->next = nullptr写的是虚拟节点，安全，返回nullptr。

全部小于 k：所有节点进 less 桶，geDummy.next为nullptr，lessTail->next被置空，geTail->next = nullptr改的是虚拟节点，不影响结果。

全部大于等于 k：less 桶为空，lessTail == &lessDummy，lessDummy.next = geDummy.next，返回geDummy.next，正确。

k 等于最小值：没有节点小于 k，退化成「全部保留原序」，仍正确。

要求「大于 k 的在前」：把条件改成cur->val > k即可，不要试图在拼接后整体反转，反转会破坏稳定性。

要求分成三段（小于、等于、大于）：用三个虚拟头，最后依次相接，逻辑相同，只是多一个桶。此时务必把最后一段的尾节点next置空。

常见坑点

1. 先改指针再保存后继

❌cur->next = lessTail->next; cur = cur->next;，原后继丢失，循环提前结束或死循环。 ✅Node* next = cur->next;保存后再挂接，最后cur = next。

2. 忘记把尾节点置空

❌ 只做lessTail->next = geDummy.next;，第二段的尾还指着原链中的节点，形成环。 ✅ 拼接后执行geTail->next = nullptr;。

3. 用<=却按<理解

❌ 题目要求「小于 k 在前」，代码写cur->val <= k，把等于 k 的节点也放到了前面。 ✅ 严格按题意选择<或<=，并在注释里写明边界归属。

4. 新建节点复制值

❌ 每个节点new Node(cur->val)，破坏了「原地重排」的要求，还多了一份内存。 ✅ 只改next指针，复用原节点。

5. 虚拟头节点用指针new出来

❌Node* dummy = new Node(0);函数结束时忘记delete，每次调用泄漏一个节点。 ✅ 在栈上定义Node lessDummy(0);，函数返回即销毁。

6. 返回值仍是原 head

❌partitionByK内部改完指针，main里继续用旧的head，而旧头可能已经被排到中间。 ✅ 返回lessDummy.next或geDummy.next，调用者用返回值更新头指针。

7. 析构时按原顺序释放

❌ 重排后仍按建表时的指针数组释放，导致重复释放或漏放。 ✅ 重排后从新头开始沿next遍历释放，delete与new一一配对。

8. 把「旋转 k 位」套用划分代码

❌ 题目要求右移 k 个位置，却按值拆分，结果完全不符。 ✅ 先确认题意；旋转应找len - k % len处的断点，再首尾相接。

总结

单链表按值重排并不需要排序，也不需要额外容器，本质是一次稳定的「分流」。把「保存后继、尾插、断尾」这三步写对，边界情况都会自然成立。真正需要花时间的是读题：确认 k 是分界值、是位移量，还是分组大小，比写代码更重要。