链表

链表题型刷题总结

注：本文仅为个人学习笔记，无任何版权。

什么是链表？

一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域，一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null

链表的头节点为head

链表的类型：

1. 单链表
2. 双链表
3. 循环链表

链表在内存中的储存方式

与数组不同，链表在内存中不是连续分布。

链表是通过指针域的指针链接在内存的各个节点，所以链表中的节点在内存中不是连续分布的，而是三楼缘分不在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义

public class ListNode {
    // 结点的值
    int val;

    // 下一个结点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

List<> xxx = new LinkedList<>();

删除节点：

只要将被删除节点的前一个节点的指针，指向后一个节点就可以了。如果要删除第n个节点，可以将第n-1个节点的指针指到第n+1个节点，java会自动释放那块内存。

添加节点：

同理，修改指针即可。

可以看出链表的增添/删除都是O(1)的操作，不会影响到其他节点。但是，如果要删除第c个节点，需要从头节点找到第c-1个节点，查找的时间复杂度为O(c)

性能分析

链表删除/插入：O(1)

链表查找： O(n)

数组删除/插入：O(n)

数组查找： O(1)

数组：数据量固定，频繁查找，较少增删

链表：数据量不固定，频繁增删，较少查找

链表的经典题目

虚拟头节点

链表操作的一大问题就是当前节点必须要找前一个节点才能操作，在这种情况下，用一个虚拟头节点可以解决这个问题。

203

链表的基本操作

一道题写一个链表ListNode的class出来，非常好的题目

707

反转链表

高频题目，递归和迭代都可以解决，建议一定熟练掌握本质。

206

删除倒数第N个节点

虚拟头节点 + 双指针，第一个指针走n 然后第二个指针跟第一个指针一起出发。

19

链表相交

很trick的方法。虽然两个链表到达相交点的距离可能不一样，但我们可以加两个链表加起来。一个指针从A遍历到B，一个指针从B遍历到A。这样他们就可以同时到达交点了！

面试题 02.07

环形链表

难点在数学证明，方法是快慢指针。很有趣的题目。

142