企业官网建设流程全解析

用 XOR 双指针反转链表：原理剖析与 C++ 源码实现（Cosmos 仓库实战）

【免费下载链接】cosmosWorld's largest Contributor driven code dataset | Used in Quark Search Engine, @OpenGenus IQ, OpenGenus Visual Project项目地址: https://gitcode.com/gh_mirrors/co/cosmos

导读

本文围绕 Cosmos 仓库 code/languages/cpp/reverse_linked_list/README.md 所讲解的核心技巧展开：如何仅用2 个指针，借助XOR（异或）位运算完成单链表反转。相比传统的 3 指针法，XOR 技巧用异或的数学性质替代了一个额外指针，把内存占用与循环体进一步压缩到极致。读完本文，你将掌握"链接反转（link reversal）"与"值交换"的本质区别、3 指针基线的完整思路、XOR 双指针的逐步推导、uintptr_t指针强转的底层原因，以及仓库中对应 C++ 源码的逐行解读与编译运行方法。

一、核心思想：反转"链接"而不是"值"

原文档开篇即点明一个容易混淆的关键前提：

我们通过**链接反转（link reversal）**来反转给定的链表，而不是通过交换链表节点的值。

这两种思路的差异在于：

• 值交换（swap values）：保持节点对象与链接结构不变，仅把data字段在两两节点间搬运。它不改变链的拓扑，只是数据搬家。
• 链接反转（link reversal）：节点与数据都不动，只把每个节点的next指针指向前驱节点，最终让整条链的走向倒转，头指针更新为原链表的尾节点。

之所以强调这一点，是因为链接反转才是所有高效反转算法（3 指针、递归、XOR 双指针）的共同基础，也决定了最终复杂度能做到O(n) 时间、O(1) 额外空间。若采用值交换，则无法在常数空间内完成，且对链表这样"指针即结构"的数据结构而言语义上并不优雅。

在 reverse_linked_list_2pointers.cpp 中可以看到，核心循环结束后还有一句至关重要的收尾：

hptr = prev; // updating the head pointer

这印证了上述思想：反转完成后，原来的尾节点（循环结束时prev停留的位置）成为新的头节点，必须更新全局头指针hptr，否则后续遍历（如print()）会从错误的起点出发。

二、链表节点结构与代码骨架

两个实现（双指针与三指针）共用了同一套节点定义与插入逻辑，定义在 reverse_linked_list_2pointers.cpp：

#include <cstdlib> #include <iostream> typedef uintptr_t ut; // 为指针位运算准备的整数别名 struct node { int data; struct node *nptr; // next 指针 }; struct node *hptr = NULL; // 全局头指针 void insertNode(int pos, int x) { struct node *temp = new node; if (temp == NULL) std::cout << "Insert not possible\n"; temp->data = x; if (pos == 1) { temp->nptr = hptr; // 头插 hptr = temp; } else { int i = 1; struct node *thptr = hptr; while (i < pos - 1) { // 找到第 pos-1 个节点 thptr = thptr->nptr; i++; } temp->nptr = thptr->nptr; // 中间插入 thptr->nptr = temp; } }

要点说明：

• pos == 1走头插分支，pos > 1走中间/尾插分支，insertNode(2, 20)会把20接在10之后，因此main()中依次insertNode(1,10) … insertNode(5,50)构造出的链表为10 -> 20 -> 30 -> 40 -> 50。
• typedef uintptr_t ut;是后续 XOR 技巧的伏笔：C/C++ 不允许对指针直接做位运算，必须先把指针强制转换成整数类型uintptr_t再异或（详见第四节）。

值得一提的是，仓库的 C++ 编码风格指南 强调使用using而非typedef、避免#include <bits/stdc++.h>、缩进使用 4 空格等约定。本文两个示例为保持与文档一致的经典写法使用了typedef与 C 风格结构体，读者在工程化改写时可参考风格指南统一风格；另外uintptr_t在标准中定义于<cstdint>，跨平台工程中建议显式包含该头文件以保证可移植性。

三、基线方法：3 指针反转（经典教科书解法）

原文档明确说明"常见的反转链表技术涉及 3 个指针"，仓库提供了对应的完整实现 reverse_linked_list_3pointers.cpp：

void reverseList() { struct node *current = hptr; struct node *next; struct node *prev = NULL; // link reversal while (current != NULL) { next = current->nptr; // 1. 先保存后继，防止断链 current->nptr = prev; // 2. 反转当前节点的链接 prev = current; // 3. prev 前移 current = next; // 4. current 前移 } // updating the head pointer after link reversal hptr = prev; }

3.1 为什么必须"先保存后继"

单链表节点只持有"下一个节点"的地址。当执行current->nptr = prev后，current原本的后继就再也找不到了，因此必须提前用next指针把后继保存下来。这就是 3 指针法需要current、prev、next三个指针的根本原因——每一个指针都承担一个不可省略的职责。

3.2 迭代过程演示

对10 -> 20 -> 30 -> 40 -> 50，每轮循环状态如下：

最终输出50 40 30 20 10，链接完全倒转。复杂度为O(n) 时间、O(1) 额外空间（仅 3 个局部指针）。

四、进阶技巧：XOR 双指针反转

原文档的核心论点是：利用 XOR 运算的性质，可以把 3 指针压缩为 2 指针，从而"消除对额外指针的需求"。仓库实现见 reverse_linked_list_2pointers.cpp：

void reverseList() { struct node *current = hptr; struct node *prev = NULL; while (current != NULL) { current = (struct node *)((ut)prev ^ (ut)current ^ (ut)(current->nptr) ^ (ut)(current->nptr = prev) ^ (ut)(prev = current)); // link reversal } hptr = prev; // updating the head pointer }

4.1 数学基础：XOR 的自反性质

XOR 位运算满足两个关键性质：

1. 自反性：a ^ a = 0；
2. 可逆性：a ^ b ^ b = a。

由此可推导出"用异或恢复原值"的模式：x ^ y ^ z中，只要知道其中任意两个，就能还原第三个。这正是经典"XOR 交换变量"技巧的原理，也是本算法消灭第三个指针的理论根基。

4.2 逐项拆解核心表达式

假设进入循环某轮时：prev = P（前驱）、current = C（当前节点）、current->nptr = N（原始后继）。则赋值语句current = (P) ^ (C) ^ (N) ^ (current->nptr = P) ^ (prev = C)中的五项分别为：

计算P ^ C ^ N ^ P ^ C，根据自反性P ^ P = 0、C ^ C = 0，结果恰为N——也就是当前节点的原始后继地址。于是：

• 表达式整体求值结果 = 原始后继N，赋给current，等价于current = next；
• 两条赋值副作用分别完成了current->nptr = prev（反转链接）与prev = current（prev 前进）。

一次表达式求值，同时完成了 3 指针法循环体内的三个动作，只用prev和current两个指针就推进了整个循环。循环退出时current == NULL，prev停留在原链表尾节点，hptr = prev完成换头。

4.3 为什么不直接对指针做异或

原文档特别强调了一个工程细节：

对于双指针技术，我们需要将指针强制转换为uintptr_t类型，然后执行位运算（此处为异或运算），因为无法直接对指针执行位运算。

原因有两点：

1. 语言层面的禁止：C/C++ 标准规定指针仅支持加减、比较、解引用等有限操作，^、&、|等位运算符对指针类型未定义，大多数编译器会直接报错或产生不可移植行为。
2. 平台相关性的消除：uintptr_t是<cstdint>（代码中经<cstdlib>引入）定义的无符号整数类型，其宽度恰好足以容纳任意指针（即sizeof(uintptr_t) == sizeof(void*)），且按位运算结果与指针二进制表示一致。将指针转为uintptr_t再异或，既合法又可跨平台复现相同结果。

代码中typedef uintptr_t ut;正是为了缩短强制转换的书写长度，让核心表达式保持紧凑可读。

五、复杂度对比与适用边界

双指针法在渐进复杂度上并不优于三指针法——两者都是 O(n)/O(1)。它的价值在于：省掉一个指针变量，体现了"用位运算性质换取更少状态"的极致优化思路，适合对内存占用极其敏感的场景（如嵌入式环境），也常被用作面试中考察位运算功底的高阶追问。

需要诚实指出的限制（从源码结构可推断）：

• 可读性与维护成本：把三句话压缩进一个含多条副作用的表达式，正确性依赖对 XOR 性质的深刻理解，后续维护者容易误读；若评价顺序被调整，行为会改变。工程实践中若追求清晰，仍推荐三指针写法。
• 适用前提：算法假设链表节点地址值不重复且允许按整数位运算，uintptr_t的取值可逆；对空链表（hptr == NULL）循环体直接跳过，hptr = prev = NULL，行为正确，无需特判。
• 示例中insertNode对new失败只打印提示而继续使用temp，属演示代码的简化处理，工程实现应检查分配结果。

六、仓库中的关联实现与扩展阅读

为便于读者在仓库内横向对比同一主题的多语言、多变体实现，以下文件与本主题直接相关：

• code/languages/cpp/reverse_linked_list/reverse_linked_list_2pointers.cpp：XOR 双指针反转（本文主解读对象）；
• code/languages/cpp/reverse_linked_list/reverse_linked_list_3pointers.cpp：三指针基线实现；
• code/data_structures/src/Linked_List/reversing_linkedlist.cpp：数据结构模块中以面向对象方式（LL类）封装的三指针反转，展示了Node(int)构造器与push头插等工程化写法；
• code/data_structures/src/Linked_List/reverse_linked_list_in_k_groups.cpp：反转每 K 个节点的进阶变体，循环体内同样使用prev/curr/temp三指针分组反转，可作为"三指针模式的实战延伸"对照阅读；
• code/data_structures/src/Linked_List/creating_linked_list.cpp、traverse_a_linked_list.cpp：链表创建与遍历的配套实现，便于构造自己的测试数据；
• guides/coding_style/c++/README.md：仓库的 C++ 编码规范，涵盖命名、缩进、头文件包含等约定，供重写风格时参考；
• test/c++/test_sample.cpp：仓库 C++ 测试目录的示例文件，展示了基于 test/c++/catch.hpp 的单元测试写法，读者可仿照其为反转算法编写断言用例。

七、编译与运行验证

两个源文件均为独立可编译的完整程序，按仓库 C++ 示例的标准流程编译运行：

# 编译三指针版本 g++ -std=c++11 reverse_linked_list_3pointers.cpp -o reverse3 ./reverse3 # 输出：50 40 30 20 10（print() 以换行分隔，即每行一个值） # 编译 XOR 双指针版本 g++ -std=c++11 reverse_linked_list_2pointers.cpp -o reverse2 ./reverse2 # 输出同样为：50 40 30 20 10

main()中构造的链表为10 -> 20 -> 30 -> 40 -> 50，两种算法反转后打印结果一致，可用于交叉验证：只要输出序列恰好逆序，即证明链接反转正确完成。若在编译时遇到uintptr_t未声明（部分编译器严格模式下<cstdlib>不保证导出该类型），补充#include <cstdint>即可。

八、总结

通过本文可以建立一条清晰的认知链路：

1. 反转链表的本质是反转链接而非交换数值；
2. 三指针法以"先保存后继"为铁律，用 3 个指针各司其职地完成迭代；
3. XOR 双指针法借助a ^ a = 0的自反性，把"取后继"这一信息压缩进一条表达式，配合对uintptr_t的强制转换合法完成指针位运算，从而将指针数从 3 降到 2；
4. 无论哪种方法，最终都要用hptr = prev更新头指针，才能让链表在新头下可被正确遍历。

该技巧的价值不在于打破 O(n) 的复杂度下限，而在于展示位运算与指针表示之间的精妙互动，是理解"指针本质上是整数地址"这一底层事实的绝佳案例。仓库中的 README 与两份 C++ 源码 完整保留了从理论到可运行代码的全过程，适合作为链表与位运算交叉训练的入门到进阶素材。

【免费下载链接】cosmosWorld's largest Contributor driven code dataset | Used in Quark Search Engine, @OpenGenus IQ, OpenGenus Visual Project项目地址: https://gitcode.com/gh_mirrors/co/cosmos