查询网站流量排名,做网站 我们的工人怎么写,湖北省住房和建设厅官方网站,做网站拉广告作者 | 王磊来源 | Java中文社群#xff08;ID#xff1a;javacn666#xff09;转载请联系授权#xff08;微信ID#xff1a;GG_Stone#xff09;链表反转是一道很基础但又非常热门的算法面试题#xff0c;它也在《剑指Offer》的第 24 道题出现过#xff0c;至于它有多… 作者 | 王磊来源 | Java中文社群IDjavacn666转载请联系授权微信IDGG_Stone链表反转是一道很基础但又非常热门的算法面试题它也在《剑指Offer》的第 24 道题出现过至于它有多热门看下面的榜单就知道了。从牛客网的数据来看链表反转的面试题分别霸占了【上周考过】和【研发最爱考】的双重榜单像网易、字节等知名互联网公司都考过但通过率却低的只有 30%所以本文我们就来学习一下反转链表的两种实现方法。排行榜数据https://www.nowcoder.com/activity/oj题目标题剑指 Offer 24. 反转链表描述定义一个函数输入一个链表的头节点反转该链表并输出反转后链表的头节点。示例:输入: 1-2-3-4-5-NULL输出: 5-4-3-2-1-NULLLeetCode 链接https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/实现方式一Stack全部入栈因为栈是先进后出的数据结构因此它的执行过程如下图所示最终的执行结果如下图所示实现代码如下所示public ListNode reverseList(ListNode head) {if (head null) return null;StackListNode 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 的实现方式是利用了栈后进先出的特性可以直接对链表进行反转实现思路和实现代码都比较简单但在性能和内存消耗方面都不是很理想可以作为笔试的保底实现方案而递归的方式在性能和内存消耗方面都有良好的表现同时它的实现代码也很简洁读者只需理解代码实现的思路即可。
往期推荐
JDK 竟然是这样实现栈的动图演示手撸堆栈的两种实现方法漫画什么是红黑树整合版关注下方二维码收获更多干货
