推荐阅读：
链表反转是一道很基础但又非常热门的算法面试题，它也在《剑指Offer》的第 24 道题出现过，至于它有多热（门）看下面的榜单就知道了。
最终的执行结果如下图所示：
实现代码如下所示：
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 的实现方式是利用了栈后进先出的特性可以直接对链表进行反转，实现思路和实现代码都比较简单，但在性能和内存消耗方面都不是很理想，可以作为笔试的保底实现方案；而递归的方式在性能和内存消耗方面都有良好的表现，同时它的实现代码也很简洁，读者只需理解代码实现的思路即可。
网友评论