23张图！万字详解「链表」，从小白到大佬！

链表和数组是数据类型中两个重要又常用的基础数据类型，数组是连续存储在内存中的数据结构，因此它的优势是可以通过下标迅速的找到元素的位置，而它的缺点则是在插入和删除元素时会导致大量元素的被迫移动，为了解决和平衡此问题于是就有了链表这种数据类型。

链表和数组可以形成有效的互补，这样我们就可以根据不同的业务场景选择对应的数据类型了。那么，本文我们就来重点介绍学习一下链表，一是因为它非常重要，二是因为面试面试必考，先来看本文的大纲：

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 image.png image.png

实现代码如下所示：

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

image.png

可以看出这种实现方法在执行效率方面已经满足我们的需求了，性能还是很高的。

实现方法 3：循环

我们也可以通过循环的方式来实现链表反转，只是这种方法无需重复调用自身方法，只需要一个循环就搞定了，实现代码如下：

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        // 最终排序的倒序链表
        ListNode prev = null;
        while (head != null) {
            // 循环的下个节点
            ListNode next = head.next;
            // 反转节点操作
            head.next = prev;
            // 存储下个节点的上个节点
            prev = head;
            // 移动指针到下一个循环
            head = next;
        }
        return prev;
    }
}

LeetCode 验证结果如下图所示：

image.png

从上述图片可以看出，使用此方法在时间复杂度和空间复杂度上都是目前的最优解，比之前的两种方法更加理想。

总结

本文我们讲了链表的定义，它是由数据域和指针域两部分组成的。链表可分为：单向链表、双向链表和循环链表，其中循环链表又可以分为单循链表和双循环链表。通过 JDK 的源码可知，Java 中的 LinkedList 其实是双向链表，我们可以使用它来实现队列或者栈，最后我们讲了反转链表的 3 种实现方法，希望本文的内容对你有帮助。