链表 LinkedList

一、链表的定义与特点

（1）链表的定义

链表通过“指针”将一组零散的内存块串联起来使用，我们把这些内存块称为链表的节点。节点的结构定义中包含两个信息，一是数据信息，用来存储数据。另一个是地址信息，用来存储下个节点的地址，一般用 next 表示。在链表结构中，有两个节点是比较特殊的：头节点 head，尾节点 tail，其中通过 head 可以遍历整个链表， tail 则指向一个空地址。

（2）链表的类别

单链表是最基础的链表形式，另外还有双向链表、循环链表和双向循环链表这几种形态。

循环链表的特点是指尾节点的指针指向链表的头节点
双向链表则是在工作中更常用的结构，在这个结构中，节点不仅存储了后继指针 next，还有一个指向前面节点的 prev。
双向循环链表则结合了前面两者的特点。

由于双向链表是在实际工作中应用更多的结构，我们更加深入的介绍下这个结构。

双向链表的特点

存储同样多的数据，双向链表会比单项链表占用更多的内存空间。
相比单向链表，更高效的可操作性。
- 这里的更加高效是指：在实际情况中，链表的删除并不是理论中的 O(1)，例如两个删除场景：1. 删除结点中“值等于某个给定值”的结点；2. 删除给定指针指向的结点。
- 在场景1中，我们必须遍历到某个节点，判断到该节点的值之后，才能真正的删除操作，而遍历查找的操作时间复杂度是O(N)，再结合删除操作O(1)，实际的时间复杂度是O(N)。
- 在场景2中，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。
- 同理，如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。
- 除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
上面的几点具体情景，也解释了为什么在实际的软件开发中，双向链表尽管消耗了更多的内存，但还是比单链表的应用更加广泛的原因。
Java 语言中的 LinkedHashMap 便是用到了双向链表。

HashMap<Integer,Integer> map = new LinkedHashMap<>();

（3）链表的操作

基本操作

插入 Insert： O(1)
删除 Delete：O(1)
随机访问 Read：O(N)
查找 Find：O(N)

（4）链表与数组的比较

数组和链表是两种截然不同的内存组织方式。但是数组和链表的对比，并不能局限于时间复杂度。我们实际的开发中，要根据具体情况，权衡究竟是选择数组还是链表。
数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。
- ArrayList 虽然支持自动扩容，但是扩容是会出现数据拷贝，而数据拷贝是非常耗时的。
- 如果你的代码对内存的使用非常苛刻，那数组就更适合你
链表本身没有大小的限制，天然地支持动态扩容，这也是它与数组最大的区别。
- 因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会更多。
- 而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。

（5）空间换时间的设计思想

在上面两个数据结构的比较中，有个更加重要的知识点需要掌握，即「空间换时间」的设计思想。

内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。
缓存实际上就是利用了空间换时间的设计思想。如果我们把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。但如果我们通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。
总结一下，对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。

二、链表的应用

（1）实现单链表反转

题目描述

Q206 反转一个单链表

解题思路

使用迭代的方法来处理链表，注意返回的变量。

代码实现

class Solution {
  // Iteratice
    public ListNode reverseList(ListNode head) {  
        ListNode pre = null;
        
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
  // Recursive
      public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

（2）合并两个有序链表

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

Q21 合并两个有序链表

解题思路

这里是使用迭代的方法来合并，关键是我们需要额外的两个变量用来保存当前的节点和待返回的节点。

代码实现

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode pre = new ListNode();
        ListNode head = pre;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                head.next = list1;
                list1 = list1.next;
            } else {
                head.next = list2;
                list2 = list2.next;
            }
            head = head.next;
        }
      
        head.next = list1 == null ? list2 : list1;  
        return pre.next;
    }
}

（3）链表的中间节点

题目描述

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

Q876 链表的中间节点

解题思路

使用双指针的方法解决。

代码实现

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

（4）删除链表的倒数第 n 个节点

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

Q19 删除链表的倒数第 n 个节点

解题思路

同样使用双指针的方法解决，但是要注意 pre 节点的使用。注意 [1], n=1 的例子，返回值不能是 head 变量。

代码实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
				ListNode pre = new ListNode(0, head);
        ListNode slow = pre;
        ListNode fast = head;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return pre.next;
    }
}

（5）判断链表中是否有环

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

Q141 环形链表

解题思路

同样是使用双指针，只需要注意边界条件就可以。

代码实现

class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next !=null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}