从链表基础到反转实战：用Python和C++实现3种反转链表算法（含递归详解）

最近在辅导几位刚入门算法的朋友时，我发现一个有趣的现象：很多人对“链表”这个数据结构感到既熟悉又陌生。熟悉是因为在教科书和面试题里频繁见到，陌生则是因为一旦要动手实现，特别是像“反转链表”这样的经典操作，各种指针（或引用）的指向就开始让人头晕目眩。这让我想起自己初学时的经历，盯着几行代码画了无数张草稿纸，才终于搞明白指针是怎么“跳舞”的。

反转链表之所以成为面试中的“常青树”，绝非偶然。它不像动态规划那样需要复杂的状态推导，也不像图论算法那样涉及庞大的数据结构。它考察的是程序员对基础数据结构的理解深度、对指针/引用操作的精准把控，以及将逻辑思维转化为代码的清晰度。一个能优雅实现链表反转的候选人，往往意味着他具备了扎实的编程基本功和清晰的逻辑链条。今天，我们就抛开那些让人望而生畏的术语，从最根本的链表概念讲起，一步步拆解三种主流的反转方法，并用Python和C++两种语言实现，看看在不同语言特性的加持下，同一逻辑如何呈现出不同的代码风貌。

1. 链表：不只是“一串珠子”

在深入反转算法之前，我们必须先统一“战场”的基本规则。链表常被比喻成一串珠子，但这个比喻容易让人忽略其动态和连接的本质。我更愿意把它想象成一列老式火车，每节车厢（节点）都载着货物（数据），并且通过挂钩（指针/引用）与下一节车厢相连。火车头（头节点）引领方向，最后一节车厢的挂钩是空着的，表示终点。

1.1 理解节点的核心：数据与指针的二元体

无论是C++还是Python，链表的基石都是“节点”。这个结构体或类只做两件事：存储数据，以及指出下一个节点在哪。

// C++ 链表节点定义
struct ListNode {
    int val;           // 存储的数据
    ListNode *next;    // 指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};

# Python 链表节点定义
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val    # 存储的数据
        self.next = next  # 指向下一个节点的引用

注意：nullptr (C++) 和 None (Python) 都表示“空”，即指针/引用不指向任何对象。这是链表结束的标志，在操作中至关重要，误用会导致访问非法内存（C++）或AttributeError（Python）。

两者的核心思想完全一致，但语法差异反映了语言哲学。C++使用明确的指针（*）和手动内存管理（虽然这里用nullptr初始化），更贴近底层；而Python使用引用，语法更简洁，内存由解释器自动管理。理解这种差异，有助于我们在实现算法时避免语言特有的陷阱。

1.2 遍历链表：与数组的根本区别

链表不支持像数组那样的随机访问（arr[i]）。要找到第n个元素，你必须从车头开始，一节车厢一节车厢地走过去。这个操作是很多链表算法的基础。

# Python 遍历链表并打印
def print_linked_list(head: ListNode):
    current = head
    while current is not None:  # 未到达终点
        print(current.val, end=" -> ")
        current = current.next  # 移动到下一节“车厢”
    print("None")  # 表示链表结束

// C++ 遍历链表并打印
void printLinkedList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) { // 未到达终点
        std::cout << current->val << " -> ";
        current = current->next; // 通过指针移动到下一个节点
    }
    std::cout << "nullptr" << std::endl;
}

遍历中的current = current->next（或current = current.next）是链表操作的精髓。它不移动数据，只移动“视线”。想象你站在一节车厢里，current就是你本人，current->next是前方车厢的门。执行这条语句，就是你走进前方车厢的过程。反转链表的核心，就是改变每一扇“门”的朝向。

2. 反转链表第一式：头插法（新建链表法）

这是最符合直觉的方法。思路很简单：准备一列新的空火车（新链表），然后把旧火车的车厢从车头开始，一节一节地拆下来，挂到新火车的车头位置。这样，旧火车最后一节车厢就会成为新车的第一节车厢，从而实现反转。

算法步骤拆解：

1. 初始化一个新火车头new_head，指向空（nullptr/None）。
2. 用一个“工程师”curr站在旧火车的当前车厢（从头开始）。
3. 在拆下curr这节车厢前，必须用next_node标记好curr后面的车厢，否则旧火车就断了。
4. 把curr这节车厢挂到新火车头new_head的前面：curr->next = new_head。
5. 更新新火车头new_head为刚挂上去的curr车厢。
6. 工程师curr移动到之前标记好的下一节车厢next_node。
7. 重复3-6步，直到旧火车所有车厢都被拆完（curr为空）。

这个过程可以用下面的表格来清晰对比每一步的状态：

步骤	旧链表 (curr)	新链表头 (new_head)	关键操作
初始	1 -> 2 -> 3 -> None	None	curr = 1, new_head = None
第1步	1 -> 2 -> 3 -> None	None	next_node = curr.next (保存2)
第1步后	2 -> 3 -> None	1 -> None	curr.next = new_head, new_head = curr
第2步	2 -> 3 -> None	1 -> None	next_node = curr.next (保存3)
第2步后	3 -> None	2 -> 1 -> None	curr.next = new_head, new_head = curr
第3步	3 -> None	2 -> 1 -> None	next_node = curr.next (保存None)
第3步后	None	3 -> 2 -> 1 -> None	curr.next = new_head, new_head = curr
结束	None	3 -> 2 -> 1 -> None	curr为None，循环结束

现在，我们来看代码实现。头插法的逻辑在两种语言中几乎是对称的。

// C++ 头插法实现
ListNode* reverseList_HeadInsert(ListNode* head) {
    ListNode* new_head = nullptr; // 新链表头，初始为空
    ListNode* curr = head;        // 遍历旧链表的指针

    while (curr != nullptr) {
        ListNode* next_node = curr->next; // **关键保存**：记住下一站，防止断链
        // 头插操作
        curr->next = new_head; // 当前节点指向新链表头
        new_head = curr;       // 更新新链表头为当前节点
        // 移动指针
        curr = next_node;      // 工程师走到旧链表下一节点
    }
    return new_head; // 返回新的链表头
}

# Python 头插法实现
def reverse_list_head_insert(head: ListNode) -> ListNode:
    new_head = None  # 新链表头，初始为空
    curr = head      # 遍历旧链表的引用

    while curr is not None:
        next_node = curr.next  # **关键保存**：记住下一站，防止断链
        # 头插操作
        curr.next = new_head  # 当前节点指向新链表头
        new_head = curr       # 更新新链表头为当前节点
        # 移动引用
        curr = next_node      # 工程师走到旧链表下一节点

    return new_head  # 返回新的链表头

提示：next_node = curr->next/curr.next 这一行是安全性的保障。如果没有它，在修改curr->next指向新链表后，我们就永远失去了访问原链表中下一个节点的途径，链表就此断裂。这就像拆车厢前，必须先记录下后面车厢的位置。

头插法的优缺点分析：

• 优点：逻辑清晰，易于理解和实现。由于创建了新链表，不会修改原链表头指针head指向的内容（但节点本身被移动了），在某些需要保留原链表的场景下更安全。
• 缺点：严格来说，它并没有“原地”反转链表，而是重新组装了节点。虽然空间复杂度仍是O(1)（只用了几个指针变量），但概念上不是纯粹的原位操作。

3. 反转链表第二式：迭代法（三指针法）

如果你追求的是纯粹、优雅的“原地”反转，迭代法是更经典的选择。它不需要新火车，而是在原有铁轨上，让每一节车厢的挂钩原地调转方向。这需要一点更精巧的指针舞蹈。

核心思想：使用三个指针prev、curr、next，在遍历过程中，逐个翻转curr节点指向prev，然后三个指针同步向前滑动。

算法步骤拆解：

1. 初始化：prev指向空（表示反转后链表的末尾），curr指向当前待反转的节点（从头开始），next临时保存curr的下一个节点。
2. 翻转：将curr->next从指向next改为指向prev。这就完成了当前节点的反转。
3. 滑动：prev移动到curr的位置，curr移动到next的位置，next再移动到新的curr的下一个节点。
4. 重复2-3步，直到curr为空。此时prev正好指向原链表的最后一个节点，即反转后的新头节点。

为了更直观，我们结合一个具体的链表 1 -> 2 -> 3 -> None 来看三指针的移动与翻转过程：

// 初始状态
prev = nullptr
curr = 1 -> 2 -> 3 -> nullptr
next = curr->next (即节点2)

// 第一轮循环：
// 翻转：1->next 从指向2 改为指向 prev(nullptr)
// 链表变为：nullptr <- 1    2 -> 3 -> nullptr
// 滑动：prev = curr (prev移动到1), curr = next (curr移动到2), next更新为curr->next (即节点3)

// 第二轮循环：
// 翻转：2->next 从指向3 改为指向 prev(1)
// 链表变为：nullptr <- 1 <- 2    3 -> nullptr
// 滑动：prev移动到2, curr移动到3, next更新为nullptr

// 第三轮循环：
// 翻转：3->next 从指向nullptr 改为指向 prev(2)
// 链表变为：nullptr <- 1 <- 2 <- 3
// 滑动：prev移动到3, curr移动到nullptr, 循环结束

// 最终，prev指向节点3，即新的头节点。

代码实现上，迭代法比头插法更简洁，因为它省去了显式的“新链表头”概念。

// C++ 迭代法（三指针）实现
ListNode* reverseList_Iterative(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;

    while (curr != nullptr) {
        ListNode* next = curr->next; // 保存下一步的起点
        curr->next = prev; // **核心翻转操作**：指针转向
        // 三指针整体前移
        prev = curr;
        curr = next;
        // next会在下一轮循环开始时重新赋值
    }
    return prev; // 循环结束时，prev指向新的头节点
}

# Python 迭代法（三指针）实现
def reverse_list_iterative(head: ListNode) -> ListNode:
    prev = None
    curr = head

    while curr is not None:
        next_node = curr.next  # 保存下一步的起点
        curr.next = prev       # **核心翻转操作**：引用转向
        # 三指针整体前移
        prev = curr
        curr = next_node
        # next_node会在下一轮循环开始时重新赋值

    return prev  # 循环结束时，prev指向新的头节点

注意：curr->next = prev 这行代码是翻转发生的唯一地点。在C++中，->是指针访问成员运算符；在Python中，.是引用访问属性运算符。它们在此处的语义是相同的：改变当前节点对下一个节点的指向。

迭代法的魅力在于其空间效率（O(1)）和逻辑的纯粹性。它直接在原链表上操作，是面试官最希望看到的“标准答案”。理解prev、curr、next三个指针如何像齿轮一样协同工作，是掌握链表操作的关键。

4. 反转链表第三式：递归法（深入理解函数调用栈）

递归法常常被认为是理解难度最高的，但它展示了算法之美——将问题分解为规模更小的相同问题。反转链表递归的核心思想是：假设我已经成功反转了从第二个节点开始的子链表，那么我只需要处理头节点和这个已反转子链表的关系即可。

递归的思考框架：

1. 基线条件（递归出口）：如果链表为空或只有一个节点，无需反转，直接返回头节点。
2. 递归步骤：假设函数能正确反转以head.next为头节点的子链表，并返回反转后的新头节点reversed_head。
3. 当前处理：现在，head节点还指向head.next（即reversed_head链表的最后一个节点）。我们需要让head.next.next（即原链表的第二个节点，现在是reversed_head链表的尾节点）指向head，然后将head.next置为None（因为head将成为新链表的尾节点）。

听起来有点绕？我们用人话和图示再解释一遍。假设链表是 1 -> 2 -> 3 -> 4 -> None。

• 递归函数reverseList(head)的任务是反转以head（节点1）开头的链表。
• 它先递归调用reverseList(head.next)，即反转 2 -> 3 -> 4 -> None。
• 关键假设：我们相信这个递归调用能正确工作，并返回反转后的子链表头reversed_head（节点4）。此时子链表状态是 4 -> 3 -> 2 -> None。
• 现在，节点1（head）还指向节点2。而节点2（head.next）现在是反转子链表的尾节点。
• 我们需要让尾节点2指向节点1：head.next.next = head。
• 然后断开节点1原来指向节点2的链接：head.next = None（因为节点1将成为整个新链表的尾节点）。
• 最后，返回reversed_head（节点4），它现在是整个链表的头。

// C++ 递归法实现
ListNode* reverseList_Recursive(ListNode* head) {
    // 基线条件：空链表或单节点链表，无需反转
    if (head == nullptr || head->next == nullptr) {
        return head;
    }

    // 递归反转以head->next开头的子链表
    ListNode* reversed_head = reverseList_Recursive(head->next);

    // 核心处理：将当前节点接在已反转子链表的末尾
    head->next->next = head; // 让子链表的尾节点指向当前节点
    head->next = nullptr;    // 当前节点成为新链表的尾节点

    return reversed_head; // 返回新的头节点（即原子链表的头）
}

# Python 递归法实现
def reverse_list_recursive(head: ListNode) -> ListNode:
    # 基线条件：空链表或单节点链表，无需反转
    if head is None or head.next is None:
        return head

    # 递归反转以head.next开头的子链表
    reversed_head = reverse_list_recursive(head.next)

    # 核心处理：将当前节点接在已反转子链表的末尾
    head.next.next = head  # 让子链表的尾节点指向当前节点
    head.next = None       # 当前节点成为新链表的尾节点

    return reversed_head  # 返回新的头节点（即原子链表的头）

递归的代码非常简洁，但理解其执行过程需要想象函数调用栈。每一次递归调用都会将当前状态压栈，直到达到基线条件才开始返回和回溯。对于链表 1->2->3->None，递归的调用栈深度为3。递归法的空间复杂度是O(n)，因为需要消耗栈空间，这在链表很长时可能成为问题（栈溢出）。

5. 三种方法的对比与实战选择

学完了三种方法，我们该如何选择？下表从多个维度进行了对比，可以帮助你根据不同场景做出决策。

特性维度	头插法 (新建链表法)	迭代法 (三指针法)	递归法
核心思想	构建新链表，旧节点逐个插入新链表头	原地翻转节点间的指针指向	将问题分解为反转子链表+处理头节点
空间复杂度	O(1) (仅用固定数量指针)	O(1) (仅用固定数量指针)	O(n) (递归调用栈深度)
时间复杂度	O(n)	O(n)	O(n)
代码简洁度	中等，逻辑直观	简洁，指针操作集中	极其简洁，但理解难度高
是否原地修改	否（节点被移动）	是	是
适用场景	理解概念、需要保留原链表引用时	面试首选、通用场景、内存敏感	链表长度可控、展示算法思维、函数式风格
语言实现差异	很小	很小	很小，但需注意递归深度限制

实战选择建议：

• 面试场景：优先使用迭代法。它效率高、代码清晰，能很好地展示你对指针操作和边界条件的把握。准备好解释prev、curr、next三个指针的作用。
• 学习理解：建议按头插法 -> 迭代法 -> 递归法的顺序学习。头插法帮你建立“反转”的物理图景；迭代法教你如何优雅地原地操作；递归法则挑战你用分治思想解决问题。
• 工程实践：对于长链表，避免使用递归法，以防栈溢出。迭代法是稳健的生产环境选择。如果语言对递归有优化（如某些函数式语言的尾递归优化），且链表长度已知较短，递归也是可读性极高的选项。

最后，无论选择哪种方法，画图都是理解链表操作的不二法门。在纸上画出每个节点的next指针如何变化，跟踪每个变量的状态，比单纯盯着代码看要有效十倍。我在最初学习时，曾为理解递归反转画了不下二十遍调用栈图，当某一次突然看透其对称之美时，那种豁然开朗的感觉至今难忘。链表反转就像编程世界里的一个经典魔术，一旦你知道了机关所在，复杂就会变得简单，困惑就会变成乐趣。