算法的学习笔记—反转链表（牛客JZ24）

😀前言
在算法面试中，链表问题是一个常见的考点，而反转链表更是其中的经典题目之一。本篇文章将通过具体的代码实现和思路解析，带你深入理解反转链表的解法。

🏠个人主页：尘觉主页

😀反转链表

NowCoder

😊问题描述

给定一个单链表的头结点 pHead，其长度为 n，要求将链表反转并返回反转后的新链表的头节点。我们需要在空间复杂度为 O(1) 和时间复杂度为 O(n) 的条件下完成这一操作。

例如，当输入链表为 {1,2,3} 时，经过反转后得到的链表应为 {3,2,1}。

以上转换过程如下图所示：

示例1

• 输入：{1,2,3}
• 输出：{3,2,1}

示例2

• 输入：{}
• 输出：{}
• 说明：空链表则输出为空。

😉解题思路

反转链表主要有两种解法：递归和迭代。下面我们将分别介绍这两种方法。

🥰递归解法

递归是一种非常自然的思维方式。在反转链表的问题中，递归的核心思想是将链表逐步缩短，并将缩短后的链表进行反转。具体来说，假设我们已经成功反转了链表的后半部分，那么我们只需要将当前节点接到反转后的链表末尾即可。

递归解法的代码实现如下：

public ListNode ReverseList(ListNode head) {// 基本情况：如果链表为空或只有一个节点，则直接返回当前节点if (head == null || head.next == null)return head;// 递归反转后续节点ListNode next = head.next;head.next = null;ListNode newHead = ReverseList(next);// 将当前节点接到反转后的链表末尾next.next = head;return newHead;
}

递归解法的分析

• 时间复杂度：O(n)。递归遍历了链表中的每一个节点，时间复杂度为 O(n)。
• 空间复杂度：O(n)。由于递归函数调用占用了系统栈空间，空间复杂度为 O(n)，不满足题目对 O(1) 空间复杂度的要求。

虽然递归解法简单直观，但由于其空间复杂度为 O(n)，不满足题目的要求。因此，在实际应用中，我们通常选择迭代解法。

🥰迭代解法

迭代解法通过头插法实现链表的反转。在遍历链表的过程中，将当前节点插入到新链表的头部，从而完成链表的反转。

迭代解法的代码实现如下：

public ListNode ReverseList(ListNode head) {// 创建一个新的空链表，用于存储反转后的节点ListNode newList = new ListNode(-1);while (head != null) {// 保存当前节点的下一个节点ListNode next = head.next;// 将当前节点插入到新链表的头部head.next = newList.next;newList.next = head;// 移动到下一个节点head = next;}// 返回新链表的头节点return newList.next;
}

迭代解法的分析

• 时间复杂度：O(n)。迭代遍历了链表中的每一个节点，时间复杂度为 O(n)。
• 空间复杂度：O(1)。由于我们只使用了常量级别的额外空间，空间复杂度为 O(1)。

迭代解法不仅满足题目对时间复杂度和空间复杂度的要求，还避免了递归深度过大的问题，是一种更为高效和实用的解决方案。

😄总结

反转链表问题是链表类题目中的经典问题，通过递归和迭代两种不同的方法，我们可以灵活应对各种场景。递归解法简单直观，但在空间复杂度上有所欠缺；而迭代解法则在时间和空间效率上更胜一筹，适合在实际工程中使用。

通过本文的学习，相信你已经掌握了反转链表的核心思路和两种主要解法。无论是在面试中还是实际开发中，希望这些技巧都能助你一臂之力。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞