单链表反转:从迭代、递归到头插、栈辅助,四种核心算法详解

📅 2026/7/31 6:36:59 👁️ 阅读次数 📝 编程学习
单链表反转:从迭代、递归到头插、栈辅助,四种核心算法详解

1. 项目概述:为什么单链表反转是面试的“必考题”?

在数据结构与算法的世界里,单链表反转绝对是一个绕不开的经典问题。我第一次在面试中被问到这个问题时,心里还嘀咕:“这不就是改几个指针的事儿吗?” 但真正动手实现,尤其是在白板上,才发现里面藏着不少细节和门道。它之所以成为面试官的心头好,不是因为它有多难,而是因为它能非常直观地考察一个程序员对指针(或引用)操作、边界条件处理、递归思想以及代码简洁性的掌握程度。无论是校招还是社招,从初级到资深,这个问题都可能以不同的形式出现,要求你用不同的方法来实现。

简单来说,单链表反转就是把一个链表的方向调转过来。原本是A -> B -> C -> D -> NULL,反转后要变成NULL <- A <- B <- C <- D,通常我们表述为D -> C -> B -> A -> NULL。这个操作本身不复杂,但实现它的方法却有好几种,每一种背后都对应着不同的编程思维。今天,我就结合自己多年的编码和面试经验,把这四种最核心的实现方法——迭代法、递归法、头插法和栈辅助法——掰开揉碎了讲清楚。我会重点解释每种方法的核心思路具体实现步骤容易踩的坑,并对比它们的优缺点和适用场景。无论你是正在准备面试,还是想巩固基础,相信这篇近万字的干货都能让你对链表操作有更深的理解。

2. 理解基石:单链表的结构与反转的核心

在深入方法之前,我们必须对操作对象有清晰的认识。单链表(Singly Linked List)是一种线性数据结构,它不像数组那样在内存中连续存储,而是通过一系列分散的“节点”(Node)通过指针串联起来。

2.1 单链表节点结构解析

一个典型的单链表节点至少包含两个部分:

  1. 数据域(data):用于存储该节点的实际值,可以是整数、字符、对象等。
  2. 指针域(next):一个指针(在C/C++中)或引用(在Java/Python等语言中),指向下一个节点。链表的最后一个节点的next域通常指向NULL(或nullptrNone等),表示链表结束。

用C语言的结构体可以这样定义:

typedef struct ListNode { int val; // 数据域,这里以整型为例 struct ListNode *next; // 指针域,指向下一个节点 } ListNode;

理解这个next指针是反转链表的关键。反转的本质,就是改变每一个节点next指针的指向,让它从指向后继节点改为指向前驱节点。

2.2 反转操作的核心逻辑与边界

反转操作的核心动作可以抽象为以下三步,假设我们当前正在操作节点curr,并且已知它的前一个节点prev

  1. 临时保存curr的下一个节点(next = curr->next)。这是最关键的一步,因为一旦我们修改了curr->next的指向,就会丢失原本后继节点的信息,链表就断开了。
  2. 改变currnext指针,让它指向prevcurr->next = prev)。这是实现“反转”的实质性操作。
  3. 更新prevcurr,为处理下一个节点做准备:prev移动到curr的位置,curr移动到之前保存的next的位置。

这个逻辑循环进行,直到curr为空。此时,prev就指向了原链表的最后一个节点,也就是新链表的头节点。

需要特别注意的边界条件:

  • 空链表:如果传入的链表头指针本身就是NULL,那么反转后还是NULL,直接返回即可。
  • 单节点链表:只有一个节点,反转后还是它自己,操作逻辑依然成立,但循环只会执行一次或递归只到一层。

脑子里有了这些基本概念和核心动作,我们就可以开始探索具体的实现方法了。不同的方法,其实就是以不同的顺序和组织方式来执行这一核心逻辑。

3. 方法一:迭代法——最直观可靠的“双指针”解法

迭代法,也被称为“双指针法”,是我最推荐首先掌握的方法。它思路清晰,效率高(时间复杂度O(n),空间复杂度O(1)),并且是理解其他方法的基础。

3.1 算法步骤与可视化推演

我们定义两个指针:prevcurr。初始时,prev指向NULL(可以想象成在新链表中,头节点之前的位置),curr指向原链表的头节点head

让我们用链表1 -> 2 -> 3 -> NULL来推演整个过程:

初始状态:prev = NULL,curr = 1(头节点)

第一轮循环:

  1. 保存curr的下一个节点:next_temp = curr->next(即节点2)。
  2. 反转指针:curr->next = prev(即1->next = NULL)。现在链表变成了:NULL <- 1, 而2 -> 3 -> NULL这部分暂时和节点1断开了,但我们用next_temp记着节点2。
  3. 指针前移:prev = curr(即prev移动到节点1),curr = next_temp(即curr移动到节点2)。 状态变为:prev = 1,curr = 2, 且NULL <- 1

第二轮循环:

  1. 保存下一个:next_temp = curr->next(节点3)。
  2. 反转指针:curr->next = prev(即2->next = 1)。链表变为:NULL <- 1 <- 23 -> NULL
  3. 指针前移:prev = 2,curr = 3

第三轮循环:

  1. 保存下一个:next_temp = curr->next(即NULL)。
  2. 反转指针:curr->next = prev(即3->next = 2)。链表变为:NULL <- 1 <- 2 <- 3
  3. 指针前移:prev = 3,curr = NULL

循环结束:此时currNULL,循环条件不满足,退出。prev指针现在指向节点3,它就是新链表的头节点。返回prev即可。

3.2 代码实现与逐行解读

这里给出C++的实现,其他语言逻辑完全一致。

/** * 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* reverseList(ListNode* head) { ListNode* prev = nullptr; // 前驱指针,初始化为空 ListNode* curr = head; // 当前指针,从头节点开始 while (curr != nullptr) { ListNode* nextTemp = curr->next; // 关键!先保存下一个节点 curr->next = prev; // 反转核心操作:当前节点指向前驱 prev = curr; // 前驱指针后移 curr = nextTemp; // 当前指针后移(到之前保存的节点) } // 循环结束时,curr为NULL,prev是原链表的尾节点,即新头节点 return prev; } };

逐行解读与注意事项:

  • ListNode* nextTemp = curr->next;:这行代码必须在修改curr->next之前执行。一旦先执行了curr->next = prev,你就再也找不到原来的curr->next了,链表会在此处丢失后续部分。这是新手最容易犯的错误之一。
  • while (curr != nullptr):循环的终止条件是curr为空,这意味着我们已经处理完了原链表的所有有效节点。
  • return prev;:为什么返回prev?因为循环结束时,curr已经移动到了NULL的位置,而prev恰好停在了最后一个被处理的节点,也就是新的头节点。
  • 空间复杂度O(1):我们只使用了固定的几个指针变量(prev,curr,nextTemp),没有使用和链表规模相关的额外空间。

实操心得:在白板或纸上画图是理解迭代法最好的方式。画几个方框代表节点,用箭头表示next指针,然后手动一步步移动prevcurr指针,并修改箭头方向。这个过程能让你对指针的操作产生肌肉记忆,面试时即使紧张也能流畅写出来。

4. 方法二:递归法——优雅但需要小心的“自底向上”解法

递归法代码非常简洁,体现了“分而治之”的思想。它将问题“反转整个链表”分解为“反转除头节点外剩余的子链表”,然后再处理头节点。理解递归需要一点抽象思维,同时也必须注意其潜在的栈溢出风险。

4.1 递归的思想与递归树分析

递归的核心思想是:假设剩余部分已经反转好了,我只需要处理当前节点。 对于链表head -> 2 -> 3 -> 4 -> NULL,递归的思路是:

  1. 我先递归调用函数,去反转以head->next(即节点2)开头的子链表2->3->4->NULL我相信这个递归调用能正确返回反转后的新头节点,假设是newHead,并且链表状态变为NULL <- 2 <- 3 <- 4(即4->3->2->NULL)。
  2. 此时,head节点(节点1)还指向节点2(即head->next现在是反转后子链表的尾节点2)。
  3. 我的任务就是把节点1接到这个已经反转好的子链表的“后面”。因为现在head->next(节点2)是子链表的尾,所以我执行head->next->next = head,让节点2指向节点1。
  4. 最后,别忘了将head->next置为NULL,因为现在节点1成了新链表的尾节点。
  5. 递归调用最终返回newHead(节点4),它就是整个链表反转后的头。

递归的终止条件:当链表为空(head == NULL)或只有一个节点(head->next == NULL)时,不需要反转,直接返回head。这是递归的“基线条件”(base case),防止无限递归。

4.2 代码实现、执行过程与栈帧分析

class Solution { public: ListNode* reverseList(ListNode* head) { // 基线条件:空链表或单节点链表,无需反转,直接返回 if (head == nullptr || head->next == nullptr) { return head; } // 递归调用:反转以head->next开头的子链表,并相信它能返回新头节点p ListNode* p = reverseList(head->next); // 递归返回后,处理当前头节点head // 此时head->next是子链表反转后的尾节点,让它指向head head->next->next = head; // 将当前节点设为新链表的尾节点 head->next = nullptr; // 返回新的头节点,这个p会一直被传递到最外层 return p; } };

执行过程与栈帧分析(以链表 1->2->3->NULL 为例):

  1. 首次调用reverseList(1)head=1,不满足基线条件,进入递归。
  2. 调用reverseList(2)head=2,不满足基线条件,继续递归。
  3. 调用reverseList(3)head=3,不满足基线条件,继续递归。
  4. 调用reverseList(NULL)head=NULL,满足基线条件,返回NULL注意:对于3->NULL这个链表,基线条件head->next == nullptr也成立,所以reverseList(3)会在下一层返回3。这里为了简化,我们走NULL分支。
  5. 回到reverseList(3)的调用栈。它收到了子链表(NULL)反转的结果p=NULL。然后执行head->next->next = head,即NULL->next = 3?这里有问题!实际上,当head=3时,head->nextNULL,对NULL解引用操作head->next->next会导致错误。这说明我们的基线条件需要修正!

正确的基线条件应该是:当head为空head->next为空时返回。对于3->NULLhead->next为空,所以reverseList(3)直接返回head(即节点3),不会执行后面的指针操作。这样才是正确的。

继续正确的流程: 4. 调用reverseList(3)head=3,head->next=NULL,满足基线条件,直接返回节点3。 5. 回到reverseList(2)。它收到p=3(子链表3->NULL反转后变成3,头是3)。此时状态:head=2head->next=3。执行head->next->next = head,即3->next = 2。执行head->next = nullptr,即2->next = NULL。现在链表是3->2->NULL。返回p=3。 6. 回到reverseList(1)。它收到p=3。此时状态:head=1head->next=2。执行2->next = 1,执行1->next = NULL。链表变为3->2->1->NULL。返回p=3

最终,p=3作为新头节点被返回。

4.3 递归法的优缺点与适用警告

优点:

  • 代码极其简洁,逻辑优雅,体现了数学归纳法的思想。
  • 在面试中写出正确的递归解法,能展示你对问题有更深层次的理解。

缺点与警告:

  • 空间复杂度O(n):由于递归调用需要系统栈保存每一层的状态,所以空间复杂度与链表长度n成正比。对于很长的链表,有栈溢出(Stack Overflow)的风险。
  • 理解难度较高:递归过程不如迭代直观,调试起来也更困难。
  • 性能开销:函数调用本身比循环有更大的开销。

注意事项:在实际工程中,尤其是处理可能很长的链表(如万级以上)时,优先使用迭代法。递归法更适合在明确链表长度有限,或作为思维练习的场景下使用。在面试中,如果你先写出了迭代法,面试官可能会追问:“能用递归实现吗?” 这时你再展示递归解法,会是一个很好的加分项。

5. 方法三:头插法——利用“虚拟头节点”的清晰解法

头插法是构建链表的一种常见技巧,反转链表可以看作是不断将原链表的节点“摘下来”,然后以“头插”的方式插入到一个新链表的头部。这种方法通常借助一个“虚拟头节点”(Dummy Node)来简化边界处理。

5.1 虚拟头节点(Dummy Node)的技巧

虚拟头节点是一个不存储实际数据的节点,它的next指针指向真正链表的头节点。引入它的好处是:

  • 统一操作逻辑:无论是对空链表、单节点还是多节点链表进行操作,都可以用同样的代码逻辑来处理dummy->next,无需单独判断head是否为空。
  • 简化指针修改:在头插过程中,新节点总是插入到dummy节点之后,这使得插入操作变得非常统一。

在反转完成后,新的链表头就是dummy->next

5.2 算法流程与逐步图解

我们仍然以链表1 -> 2 -> 3 -> NULL为例,使用头插法。

初始状态:创建一个虚拟头节点dummydummy->next = nullptrcurr指针指向原链表头head(节点1)。

第一步:

  1. 保存curr的下一个节点:nextTemp = curr->next(节点2)。
  2. 头插操作:将curr节点插入到新链表(dummy之后)的头部。
    • curr->next = dummy->next。此时dummy->nextNULL,所以1->next = NULL
    • dummy->next = curr。即dummy->next = 1。 现在,新链表为dummy -> 1 -> NULL。原链表剩余2 -> 3 -> NULLcurr原本指向1,但已被“摘走”)。
  3. curr移动到之前保存的nextTemp,即节点2。

第二步:

  1. nextTemp = curr->next(节点3)。
  2. 头插节点2:
    • curr->next = dummy->nextdummy->next现在是节点1,所以2->next = 1
    • dummy->next = curr。即dummy->next = 2。 新链表变为dummy -> 2 -> 1 -> NULL
  3. curr移动到节点3。

第三步:

  1. nextTemp = curr->next(NULL)。
  2. 头插节点3:
    • curr->next = dummy->nextdummy->next是节点2,所以3->next = 2
    • dummy->next = curr。即dummy->next = 3。 新链表变为dummy -> 3 -> 2 -> 1 -> NULL
  3. curr移动到NULL,循环结束。

最终,反转后的链表头是dummy->next,即节点3。

5.3 代码实现与对比迭代法

class Solution { public: ListNode* reverseList(ListNode* head) { ListNode dummy(0); // 创建一个虚拟头节点,值任意,这里用0 ListNode* curr = head; while (curr != nullptr) { ListNode* nextTemp = curr->next; // 保存下一个 // 头插操作:将curr插入到dummy节点之后 curr->next = dummy.next; // curr指向原dummy后的第一个节点 dummy.next = curr; // dummy指向curr,curr成为新的第一个节点 curr = nextTemp; // 处理原链表的下一个节点 } return dummy.next; // 返回新链表的真实头节点 } };

头插法与迭代法的对比:

  • 逻辑视角不同:迭代法是“就地”反转,通过两个指针一前一后滑动并修改指向。头插法是“新建”一个链表(从dummy开始),不断将原链表的节点搬运过来。
  • 边界处理:头插法因为引入了dummy节点,代码中几乎不需要对head为空的情况做特殊判断(while循环条件已经处理)。迭代法虽然也简单,但初始时prevNULL的逻辑需要理解。
  • 本质一致:如果你仔细观察,头插法中的curr->next = dummy.nextdummy.next = curr这两个操作,与迭代法中curr->next = prevprev = curr在效果上是类似的。dummy.next扮演了迭代法中prev的角色。可以说,头插法是迭代法的一种变体,只是引入了一个固定的“锚点”dummy

实操心得:虚拟头节点技巧在解决链表问题时非常强大,例如“删除链表倒数第N个节点”、“合并两个有序链表”等问题中,都能让代码更简洁健壮。掌握它,是成为链表问题熟手的重要一步。

6. 方法四:栈辅助法——利用栈“后进先出”特性的直观解法

栈(Stack)是一种“后进先出”(LIFO)的数据结构。单链表反转,正好符合这个特性:原链表的尾节点应该成为新链表的头节点,即最后遍历到的节点最先被取出。我们可以利用栈来临时存储所有节点,再依次弹出构建新链表。

6.1 栈的特性与反转的天然契合

算法的思路非常直接:

  1. 遍历入栈:从头到尾遍历原链表,将每个节点依次压入栈中。
  2. 出栈重构:依次从栈中弹出节点。第一个弹出的节点是原链表的尾节点,将其作为新链表的头节点。之后每弹出一个节点,就把它连接到当前已构建的新链表的末尾。

这个过程就像把一摞书从下到上按顺序放入箱子(栈),然后再从箱子里一本一本拿出来,拿出来的顺序就正好是反的。

6.2 详细实现步骤与复杂度分析

#include <stack> // 需要包含栈的头文件 class Solution { public: ListNode* reverseList(ListNode* head) { if (head == nullptr) return nullptr; // 处理空链表 std::stack<ListNode*> nodeStack; ListNode* curr = head; // 第一步:遍历链表,所有节点入栈 while (curr != nullptr) { nodeStack.push(curr); curr = curr->next; } // 第二步:出栈,构建新链表 // 栈顶元素是原链表的尾节点,作为新链表的头 ListNode* newHead = nodeStack.top(); nodeStack.pop(); ListNode* tail = newHead; // tail用于追踪新链表的末尾,方便连接新节点 tail->next = nullptr; // 初始化新链表尾 while (!nodeStack.empty()) { ListNode* node = nodeStack.top(); nodeStack.pop(); tail->next = node; // 将弹出的节点接到新链表尾部 tail = node; // 更新尾指针 tail->next = nullptr; // 确保新尾节点的next为空 } return newHead; } };

复杂度分析:

  • 时间复杂度 O(n):遍历链表入栈 O(n),出栈构建新链表 O(n),总体是 O(2n) = O(n)。
  • 空间复杂度 O(n):需要使用一个额外的栈来存储所有 n 个节点的指针。这是该方法最大的缺点。

6.3 栈方法的评价与应用场景

优点:

  • 思路极其直观,符合人类“逆序”的直觉,容易理解和记忆。
  • 代码逻辑清晰,几乎就是“描述”的直译。

缺点:

  • 空间复杂度高,需要O(n)的额外空间。在内存受限或链表极长的场景下不适用。
  • 性能上需要两次完整的遍历和栈操作,常数项时间开销比迭代法大。

应用场景:

  • 作为一种教学示例,帮助初学者理解反转的概念和栈的应用。
  • 在某些特定环境下,如果栈结构已经存在或被广泛使用,且链表长度可控,这也是一种可选的方案。
  • 面试中,如果你在写出迭代和递归后,被问到“还有别的方法吗?”,可以提出栈方法,并清晰地分析其空间复杂度劣势,这能展示你思维的广度。

注意事项:使用栈方法时,要特别注意节点next指针的清理。在将节点压栈时,它的next指针还指向原链表中的下一个节点。在出栈后构建新链表时,必须正确设置每个节点的next指针,否则可能形成环或内存访问错误。上面的代码在将节点接入新链表后,立即将其next置为nullptr,是一种安全的做法。

7. 四种方法综合对比与实战选择指南

现在我们已经掌握了四种反转单链表的方法,是时候做一个全面的复盘和对比了。选择哪种方法,取决于具体的场景、约束条件以及个人偏好。

7.1 性能、空间与代码复杂度对比

特性迭代法 (双指针)递归法头插法 (虚拟头节点)栈辅助法
时间复杂度O(n)O(n)O(n)O(n)
空间复杂度O(1)O(n) (系统调用栈)O(1)O(n) (显式栈)
思路直观性较直观,需理解指针滑动较抽象,需理解递归栈直观,类似新建链表最直观,符合逆序直觉
代码简洁性简洁最简洁简洁较繁琐
边界处理容易需注意基线条件最容易(虚拟头节点)容易
适用场景通用首选,工程推荐链表不长,展示思维深度工程中常用,逻辑清晰教学、思维拓展

核心结论:

  1. 工程实践首选迭代法或头插法。它们具有常数级的空间复杂度,性能最优,代码也足够清晰健壮。两者本质相通,头插法因虚拟节点而更统一。
  2. 递归法是展示算法思维和代码优雅性的利器,但受限于栈深度,不适合处理长链表。在面试中可作为第二种解法提出。
  3. 栈方法空间开销大,在实际工程中很少用于单纯的链表反转,但其思想在解决“逆序打印”、“判断回文链表”等衍生问题时可能有用。

7.2 面试实战策略与高频变种问题

在面试中遇到链表反转,建议按以下策略应对:

  1. 首先写出迭代法。这是最稳妥、最被认可的方法。边写边解释prev,curr,nextTemp三个指针的作用。
  2. 主动分析复杂度。说完实现后,主动说明时间O(n),空间O(1)。
  3. 等待或主动询问。面试官可能会直接问“还有别的方法吗?”,或者在你完成后沉默。这时你可以说:“除了迭代,还可以用递归的思想来解决。”
  4. 写出递归法。清晰地写出基线条件和递归公式。务必指出递归的缺点:“递归代码更简洁,但由于需要系统栈,空间复杂度是O(n),对于长链表可能有栈溢出风险,所以工程上迭代法更安全。”
  5. 展示知识广度。如果面试官还有兴趣,可以简要提一下头插法和栈的思路,并对比优劣。

常见变种与关联问题:

  • 反转链表的一部分(LeetCode 92):反转从位置mn的链表。这需要你先找到第m-1个节点,然后截取子链表进行反转,最后再拼接回去。迭代法是实现的基础。
  • K个一组反转链表(LeetCode 25):每k个节点一组进行反转,不足k的保持原样。这需要你熟练掌握反转一个子链表的操作(迭代法),并处理好组与组之间的连接。
  • 判断回文链表(LeetCode 234):一种常见解法是找到中点,反转后半部分,然后比较前后两部分。这里直接使用了链表反转作为子过程。
  • 两数相加 II(LeetCode 445):数字存储在链表中,且高位在前。可以先反转链表,使其变成低位在前,然后使用“两数相加 I”(LeetCode 2)的解法,最后再反转结果链表。

掌握好单链表反转这一基础操作,是解决上述所有更复杂问题的前提。

8. 常见问题、调试技巧与深度避坑指南

即使理解了算法,自己实现时也可能遇到各种问题。这里我总结了一些常见的“坑”和调试技巧。

8.1 指针操作中的经典错误

  1. 丢失后继节点(最经典)

    // 错误代码 curr->next = prev; // 先反转了指针 ListNode* nextTemp = curr->next; // 此时curr->next已经是prev了,不是原后继! curr = nextTemp; // 错误移动

    结果curr错误地指向了prev,链表遍历中断或形成环。修正:必须先保存再修改

  2. 形成环状链表: 在递归法或某些迭代实现中,如果忘记将新链表的尾节点(原头节点)的next置为NULL,会导致链表成环。例如在递归法中,如果忘记head->next = nullptr,原头节点1的next可能还指向2,而2的next又指向1,形成环。

  3. 返回错误头节点: 迭代法循环结束后返回的是prev,不是curr。头插法返回的是dummy.next,不是dummy。递归法返回的是最底层递归调用传回来的p

8.2 递归相关的陷阱

  1. 基线条件错误: 只判断if (head == nullptr)对于单节点链表是不够的。对于单节点链表1->NULLhead->nextNULL,如果进入递归体执行head->next->next = head就会对NULL解引用,导致运行时错误。正确的基线条件是if (head == nullptr || head->next == nullptr)

  2. 栈溢出: 这是递归法的固有风险。对于长度超过系统栈容量(通常几千到几万层)的链表,程序会崩溃。这是不推荐在工程中对长链表使用递归的主要原因。

8.3 调试方法与单元测试建议

  1. 画图,画图,再画图!对于指针问题,在纸上画出每个节点的valnext指针,一步步演算算法的执行过程。这是最有效的调试手段。
  2. 打印链表辅助函数: 编写一个简单的printList(ListNode* head)函数,遍历链表并打印每个节点的值。在反转前和反转后分别打印,可以快速验证结果。
    void printList(ListNode* head) { ListNode* curr = head; while (curr) { std::cout << curr->val << " -> "; curr = curr->next; } std::cout << "NULL" << std::endl; }
  3. 使用哨兵值测试: 不要只测试1->2->3。构造全面的测试用例:
    • 空链表:NULL
    • 单节点链表:1->NULL
    • 双节点链表:1->2->NULL
    • 长链表
    • 包含相同值的链表:1->1->1->NULL
  4. 内存泄漏检查(对于C/C++): 如果是在需要手动管理内存的环境下,确保反转操作不会导致节点丢失。反转本身不创建新节点,只是改变指针,所以通常不会引起泄漏。但如果你在测试代码中自己new了节点,记得最后要delete

8.4 一个综合案例:修复有问题的递归代码

假设你看到如下有Bug的递归代码:

ListNode* reverseList(ListNode* head) { if (head == nullptr) return nullptr; // 基线条件1 ListNode* newHead = reverseList(head->next); // 递归反转子链表 // 假设这里忘记处理 head->next->next 和 head->next return newHead; // 总是返回子链表的头? }

问题分析:这段代码递归调用了,但递归返回后没有做任何指针修改操作,只是把子链表的头原样返回。所以对于链表1->2->3,它最终返回的是3,但链表结构根本没变,还是1->2->3,只是函数返回了节点3的地址。修正:必须在递归调用返回后,执行指针重定向操作,并将新的头节点(原尾节点)正确传递回来。正确的代码见第4.2节。

链表反转是一个完美的“小题目,大道理”的范例。它考察的是程序员对基础数据结构的理解、对指针的掌控力、思维的严谨性以及对不同编程范式的掌握。我建议每一位开发者都不要满足于仅仅“写出”一种解法,而是真正去理解每一种解法背后的思想,并能在白板上清晰无误地实现它。当你对这个问题了如指掌时,你会发现很多复杂的链表问题,其核心模块之一就是这段反转逻辑。