当前位置： 首页 > news >正文

Leetcode 16 java

news 2025/8/19 18:46:27

再来重做错题，我觉得做错题真的有点痛苦......菜就多练！

206. 反转链表

相关企业

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

1 我的想法

一眼hash我没救了我是猪，怎么会，这哪跟哪啊？太好笑了。

一般这种情况就是迭代吧。

类似于之前做过的翻转二叉树，只不过翻转二叉树是左右节点root.left和root.right相互交换，这里是链表应该是next前后交换，后面的每一个节点往前走，前后互换就好了，判断条件是next节点是否为空。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}

恩这就是官方的迭代题解。

和我想得一样吧。

手敲一遍。

ListNode prev = null;

ListNode curr = head;

if (curr == null ){

return null;
}

else{

ListNode next= curr.next;

curr.next = prev;

prev = curr;

curr = next;

return next;//不知道写对没有。写错了！

}

2 反转链表（错题重做解析）

针对 “反转链表” 这道题，我们先分析你手写代码的问题，再明确迭代法的核心逻辑，最后补充递归解法，帮你彻底掌握两种思路。

一、先修正你的手写代码问题

你手写的代码缺少循环逻辑，仅处理了 “头节点→第一个节点” 的单次反转，无法完成整个链表的遍历反转，且返回值错误。具体问题如下：

  1. 无循环结构：链表反转需要遍历所有节点（从 head 到最后一个节点），仅靠 if-else 只能处理 0 个或 1 个节点的情况，无法处理多节点链表（如示例 1 的 [1,2,3,4,5]）。
  2. 返回值错误：循环结束后，curr 会指向 null，prev 才是反转后链表的新头节点（最后一个原始节点），所以应返回 prev，而非 next。

二、迭代法（正确版 + 核心逻辑）

迭代法的核心是用 3 个指针（prev/curr/next）逐步反转节点指向，避免链表断裂。

正确代码

java

运行

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {// 1. 初始化：prev指向null（反转后链表的末尾），curr指向原链表头ListNode prev = null;ListNode curr = head;// 2. 遍历原链表：直到curr指向null（遍历完所有节点）while (curr != null) {// 先保存curr的下一个节点（防止反转后丢失后续链表）ListNode next = curr.next;// 反转curr的指向：从“指向next”改为“指向prev”curr.next = prev;// 指针后移：prev跟进到curr，curr跟进到之前保存的nextprev = curr;curr = next;}// 3. 循环结束后，prev是反转后链表的新头节点return prev;}
}
逻辑拆解（以示例 1 [1,2,3,4,5] 为例）
  • 初始状态：prev=null, curr=1, next=2
  • 第 1 次循环：1.next=null → prev=1, curr=2
  • 第 2 次循环：2.next=1 → prev=2, curr=3
  • 第 3 次循环：3.next=2 → prev=3, curr=4
  • 第 4 次循环：4.next=3 → prev=4, curr=5
  • 第 5 次循环：5.next=4 → prev=5, curr=null（循环结束）
  • 最终返回 prev=5，即反转后的链表头 [5,4,3,2,1]。

三、递归法（进阶解法）

递归法的核心是 **“先反转后面的链表，再调整当前节点的指向”**，利用递归栈回溯时完成反转。

代码实现

java

运行

class Solution {public ListNode reverseList(ListNode head) {// 递归终止条件：空链表 或 只有1个节点（无需反转）if (head == null || head.next == null) {return head;}// 1. 递归反转“当前节点的下一个节点开始的子链表”ListNode newHead = reverseList(head.next);// 2. 调整当前节点与子链表的指向（关键步骤）head.next.next = head; // 让子链表的尾节点（原head.next）指向当前节点head.next = null;      // 切断当前节点与原next的联系，避免环// 3. 返回反转后链表的新头节点（始终是原链表的最后一个节点）return newHead;}
}
逻辑拆解（以示例 2 [1,2] 为例）
  1. 调用 reverseList(1) → 因 1.next≠null，继续调用 reverseList(2)。
  2. 调用 reverseList(2) → 因 2.next=null，返回 2（newHead=2）。
  3. 回溯到 reverseList(1)：
    • 执行 1.next.next = 1 → 即 2.next=1（完成反转）。
    • 执行 1.next=null → 避免 1 指向 2 形成环。
  4. 返回 newHead=2，最终结果 [2,1]。

四、总结

  • 迭代法：时间复杂度 O (n)（遍历一次链表），空间复杂度 O (1)（仅用 3 个指针），是更常用的解法（无递归栈开销）。
  • 递归法：时间复杂度 O (n)（递归 n 次），空间复杂度 O (n)（递归栈深度），思路更巧妙但需理解 “回溯调整”。

下次遇到链表操作，先想 “指针如何移动才能避免断裂”，多画几步流程（比如用草稿纸写 prev/curr/next 的变化），会比直接写代码更清晰～

3 在 “反转链表” 问题中，if 和 while 不能混用

在 “反转链表” 问题中，if 和 while 不能混用，核心区别在于它们的 “执行次数” 和 “适用场景” 完全不同，这也是你之前手写代码出错的关键原因，具体可以从这两点理解：

1. 先明确：if 和 while 的本质区别

  • if 是 “判断一次，执行一次”：只检查一次条件，满足就执行内部代码，之后直接跳出（无论后续条件是否还满足）。
    比如你之前写的 if (curr == null)，只能处理 “空链表” 或 “单个节点” 的情况 —— 一旦链表有 2 个及以上节点（如 [1,2]），if 只能反转 1 次（把 1 指向 null），但无法继续处理 2 指向 1 的步骤，链表会断裂。

  • while 是 “判断多次，循环执行”：会反复检查条件，只要条件满足就持续执行内部代码，直到条件不满足才跳出。
    反转链表需要遍历所有节点（从 head 到最后一个节点），每个节点都要执行 “保存 next → 反转指向 → 指针后移” 这三步。while (curr != null) 刚好能实现 “逐个处理节点，直到遍历完”，这是 if 做不到的。

2. 举个直观例子：用 if 处理 [1,2] 会失败

假设用 if 替代 while，代码逻辑会变成这样（对应你之前的思路）：

java

运行

// 错误示例：用 if 替代 while
ListNode prev = null;
ListNode curr = head; // head = 1
if (curr != null) { // 条件满足，执行一次ListNode next = curr.next; // next = 2curr.next = prev; // 1 → nullprev = curr; // prev = 1curr = next; // curr = 2
}
// 执行完 if 后，代码直接结束
return next; // 此时 next=2，但 2 的 next 还是指向 1 吗？不！2 的 next 依然是 null（原链表的初始状态）

最终结果会是 [2]（而非正确的 [2,1]）—— 因为 if 只执行了 1 次，没机会处理 “让 2 的 next 指向 1” 这步，链表直接断裂。

3. 结论：只有 while 能满足需求

反转链表的核心是 “遍历所有节点”，而遍历需要 “重复执行相同逻辑直到结束”—— 这正是 while 的场景（循环执行），if 因 “只执行一次” 无法完成多节点的连续反转。

简单记：单次判断用 if，重复判断用 while，链表遍历、数组遍历等 “需要逐个处理元素” 的场景，几乎都要用 while（或 for，本质也是循环）。

4 之前翻转二叉树却可以用if递归

翻转二叉树用递归（带 if 判断）能成，而反转链表用单纯的 if 不行，核心原因是两者的 “结构特性” 和 “处理逻辑” 完全不同，我们可以从三个角度对比理解：

1. 先看 “翻转二叉树” 为什么能用递归（带 if）

翻转二叉树的核心逻辑是：“交换当前节点的左右子树，再递归交换左子树和右子树”，代码大致是这样：

java

运行

public TreeNode invertTree(TreeNode root) {// 递归终止条件（用 if 判断）if (root == null) {return null;}// 交换当前节点的左右子树TreeNode temp = root.left;root.left = root.right;root.right = temp;// 递归处理左子树和右子树invertTree(root.left);  // 处理左子树的翻转invertTree(root.right); // 处理右子树的翻转return root;
}

这里的 if 是递归终止条件（避免对 null 节点操作），而真正实现 “全树翻转” 的是递归调用本身—— 通过 invertTree(root.left) 和 invertTree(root.right)，把 “翻转” 操作自动传递到所有子节点，本质上是用 “函数调用栈” 替代了 “循环”，实现了对所有节点的遍历。

2. 再看 “反转链表” 为什么单纯 if 不行

链表是线性结构（每个节点只有一个 next 指针），反转的核心是 **“从第一个节点到最后一个节点，逐个调整 next 指向”**，必须按顺序处理（不能像二叉树那样 “左右子树并行递归”）。

如果只用 if 不用循环 / 递归，最多只能处理 1 个节点的指向调整（比如把 1→2 改成 1→null），但无法继续处理 2→1（因为没有机制让代码 “自动跳到下一个节点”）。

但反转链表也能用递归（本质是用递归栈模拟循环），比如之前提到的递归解法：

java

运行

public ListNode reverseList(ListNode head) {// 递归终止条件（用 if 判断）if (head == null || head.next == null) {return head;}// 递归处理后续节点（核心：让代码“自动跳到下一个节点”）ListNode newHead = reverseList(head.next);// 调整当前节点指向head.next.next = head;head.next = null;return newHead;
}

这里的 if 同样是递归终止条件，而真正实现 “遍历所有节点” 的是 reverseList(head.next)—— 通过递归调用，让代码 “沿着链表一个个往后走”，本质和循环的 “curr = next” 效果一致。

3. 关键区别总结

对比项翻转二叉树（递归）反转链表（迭代 / 递归）
结构特性非线性（每个节点有两个分支）线性（每个节点只有一个后继）
处理逻辑交换左右子树后，并行递归左右子树按顺序逐个调整指针，需依次处理
if 的作用递归终止条件（避免操作 null）同样是递归终止条件（或边界判断）
遍历机制靠递归调用覆盖所有子节点迭代靠 while 循环，递归靠 head.next 传递

简单说：两者都能用 if 做终止判断，但二叉树的递归天然能遍历所有节点（因为左右子树的递归会自动扩散），而链表必须靠 “循环” 或 “递归调用传递” 才能遍历所有节点。

你之前写链表代码时，只用到了 if 做单次判断，却没加 “循环” 或 “递归调用” 来遍历后续节点，所以才会出错～

-----------------------------------------------------------------

结尾，手敲一遍巩固一下。


ListNode prev = null;
ListNode curr = head;
while (curr != null) { 
    ListNode next = curr.next; 
    curr.next = prev; 
    prev = curr; 
    curr = next; 
}
return prev;

http://www.xdnf.cn/news/1324477.html

相关文章：

  • Effective C++ 条款49：了解new-handler的行为
  • 力扣 hot100 Day77
  • 单片机驱动LCD显示模块LM6029BCW
  • 机器翻译论文阅读方法：顶会（ACL、EMNLP）论文解析技巧
  • STM32学习笔记14-I2C硬件控制
  • 大数据计算引擎（四）—— Impala
  • Fluss：颠覆Kafka的面向分析的实时流存储
  • GPT-5之后：当大模型更新不再是唯一焦点
  • 深度学习必然用到的概率知识
  • Vue 3中watch的返回值：解锁监听的隐藏技巧
  • 敏感数据加密平台设计实战：如何为你的系统打造安全“保险柜”
  • 遥感机器学习入门实战教程 | Sklearn 案例②：PCA + k-NN 分类与评估
  • Day8--滑动窗口与双指针--1004. 最大连续1的个数 III，1658. 将 x 减到 0 的最小操作数，3641. 最长半重复子数组
  • 具身智能2硬件架构（人形机器人）摘自Openloong社区
  • Next.js 中的 SEO：搜索引擎优化最佳实践
  • flutter项目适配鸿蒙
  • JMeter与大模型融合应用之构建AI智能体：评审性能测试脚本
  • 【Jenkins】03 - 自动构建和docker构建
  • MCP协议演进：从SSE到Streamable HTTP的技术革命
  • 宁波市第八届网络安全大赛初赛（REVERSE-Writeup)
  • FPGA-Vivado2017.4-建立AXI4用于单片机与FPGA之间数据互通
  • OpenTelemetry、Jaeger 与 Zipkin：分布式链路追踪方案对比与实践
  • vscode wsl解决需要用别的用户调试的问题
  • VSCode REST Client 使用总结
  • Linux下的软件编程——IPC机制
  • Linx--MySQL--安装笔记详细步骤！
  • k8sday10服务发现（1/2）
  • 数据泵实施VPS海外：跨国数据同步的完整解决方案
  • 45 C++ STL模板库14-容器6-容器适配器-优先队列(priority_queue)
  • 系统架构评估方法全景解析