写点什么

链表反转的两种实现方法,后一种击败了 100% 的用户

用户头像
小Q
关注
发布于: 2020 年 10 月 13 日

链表反转是一道很基础但又非常热门的算法面试题,它也在《剑指Offer》的第 24 道题出现过,至于它有多热(门)看下面的榜单就知道了。





点击并拖拽以移动



从牛客网的数据来看,链表反转的面试题分别霸占了【上周考过】和【研发最爱考】的双重榜单,像网易、字节等知名互联网公司都考过,但通过率却低的只有 30%,所以本文我们就来学习一下反转链表的两种实现方法。

文末附算法面试参考文档+源码获取方式:含剑指offer

题目

标题:剑指 Offer 24. 反转链表

描述:定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

LeetCode 链接:leetcode-cn.com/problems/fa…

实现方式一:Stack





点击并拖拽以移动



全部入栈:





点击并拖拽以移动



​ 因为栈是先进后出的数据结构,因此它的执行过程如下图所示:





点击并拖拽以移动





点击并拖拽以移动





点击并拖拽以移动



​ 最终的执行结果如下图所示:





点击并拖拽以移动



​ 实现代码如下所示:

public ListNode reverseList(ListNode head) {
if (head == null) return null;
Stack<ListNode> stack = new Stack<>();
stack.push(head); // 存入第一个节点
while (head.next != null) {
stack.push(head.next); // 存入其他节点
head = head.next; // 指针移动的下一位
}
// 反转链表
ListNode listNode = stack.pop(); // 反转第一个元素
ListNode lastNode = listNode; // 临时节点,在下面的 while 中记录上一个节点
while (!stack.isEmpty()) {
ListNode item = stack.pop(); // 当前节点
lastNode.next = item;
lastNode = item;
}
lastNode.next = null; // 最后一个节点赋为null(不然会造成死循环)
return listNode;
}
复制代码



点击并拖拽以移动

LeetCode 验证结果如下图所示:





点击并拖拽以移动



实现方式二:递归





点击并拖拽以移动





点击并拖拽以移动





点击并拖拽以移动





点击并拖拽以移动





点击并拖拽以移动



​ 实现代码如下所示:

public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
// 从下一个节点开始递归
ListNode reverse = reverseList(head.next);
head.next.next = head; // 设置下一个节点的 next 为当前节点
head.next = null; // 把当前节点的 next 赋值为 null,避免循环引用
return reverse;
}
复制代码



点击并拖拽以移动

LeetCode 验证结果如下图所示:





点击并拖拽以移动



​总结

本文我们分别使用了 Stack 和递归的方法实现了链表反转的功能,其中 Stack 的实现方式是利用了栈后进先出的特性可以直接对链表进行反转,实现思路和实现代码都比较简单,但在性能和内存消耗方面都不是很理想,可以作为笔试的保底实现方案;而递归的方式在性能和内存消耗方面都有良好的表现,同时它的实现代码也很简洁,读者只需理解代码实现的思路即可。

粉丝福利

现在面试大厂,算法几乎成为是必考题,尤其是像腾讯和字节这种算法大牛,更是对算法要求的更加严格一些,这里给大家推荐三份算法文档+源码

需要这三份资料的,关注公众号:Java架构师联盟,即可查看资料获取方式

剑指offer





点击并拖拽以移动



力扣前400道算法笔记





点击并拖拽以移动





点击并拖拽以移动





点击并拖拽以移动



左程云算法





点击并拖拽以移动





点击并拖拽以移动



发布于: 2020 年 10 月 13 日阅读数: 31
用户头像

小Q

关注

还未添加个人签名 2020.06.30 加入

小Q 公众号:Java架构师联盟 作者多年从事一线互联网Java开发的学习历程技术汇总,旨在为大家提供一个清晰详细的学习教程,侧重点更倾向编写Java核心内容。如果能为您提供帮助,请给予支持(关注、点赞、分享)!

评论

发布
暂无评论
链表反转的两种实现方法,后一种击败了100%的用户