链表反转的两种实现方法，后面这种击败了100%的用户！

推荐阅读：

我总结了72份面试题，累计3170页，斩获了30+互联网公司offer（含BATJM）

2020首战告捷,这份Java面试神技Plus版，让我成功拿到了阿里、京东、字节跳动等大厂offer

膜拜！阿里内部都在强推的K8S(kubernetes)学习指南，不能再详细了

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

从牛客网的数据来看，链表反转的面试题分别霸占了【上周考过】和【研发最爱考】的双重榜单，像网易、字节等知名互联网公司都考过，但通过率却低的只有 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

全部入栈：

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

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

实现代码如下所示：

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 的实现方式是利用了栈后进先出的特性可以直接对链表进行反转，实现思路和实现代码都比较简单，但在性能和内存消耗方面都不是很理想，可以作为笔试的保底实现方案；而递归的方式在性能和内存消耗方面都有良好的表现，同时它的实现代码也很简洁，读者只需理解代码实现的思路即可。