关于java:链表反转的两种实现方法后一种击败了100的用户

61次阅读

共计 1381 个字符，预计需要花费 4 分钟才能阅读完成。

链表反转是一道很根底但又十分热门的算法面试题，它也在《剑指 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/

全副入栈：

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

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

实现代码如下所示：

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