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

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

image.png


image.png

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

排行榜数据:https://www.nowcoder.com/activity/oj

题目

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

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

示例:

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

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

LeetCode 链接:https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

实现方式一:Stack

image.png

全部入栈:

image.png


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

image.png


image.png


image.png


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

image.png


实现代码如下所示:

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 验证结果如下图所示:

image.png

实现方式二:递归

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wspxzf.html