算法——链表篇

1、链表理论基础

定义

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

链接的入口节点称为链表的头结点也就是head。

如图所示：

链表的类型

单链表

刚刚说的就是单链表，单向链表，只能从上一个节点得到下一个节点，不能从下一个节点得到上一个节点。

双链表

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

既能从上一个节点得到下一个节点，又能从下一个节点得到上一个节点，双向链表。

如图所示：

循环链表

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

如图所示：

链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

如图所示：

这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。

链表的实现

Java版链表实现：

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2、链表的操作

删除节点

删除D节点，如图所示：

链表删除节点其实很简单，以删除D节点为例，只需找到该节点的上一个节点（C节点），使得next指向该节点的下一个节点（E节点）即可。

那D节点不是依然存留在内存里么？只不过是没有在这个链表里而已？

Java语言有自己的内存回收机制，会自动帮我们回收不用自己手动释放了

添加节点

如图所示：

添加F节点至C、D节点中。将C节点next指向F节点，F节点next指向D节点即可。

可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

性能分析

链表的特性和数组的特性进行一个对比，如图所示：

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

3、移除链表元素

203.移除链表元素

力扣题目链接

题意：删除链表中等于给定值 val 的所有节点。

示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

思路

移除节点，可分为两种情况，一种是头节点，一种是非头节点

因此第一种解法：分情况讨论，删除头节点和非头节点（直接使用原来的链表来进行删除操作。）

因为头节点已经没有前一个节点了，头节点满足条件直接将下一个节点赋值给头节点即可，非头结点满足条件直接让该节点上一个节点指向该节点下一个节点即可。

代码实现

public ListNode removeElements(ListNode head, int val) {
          if(head == null){
          return null;
          }  
        //头节点删除方式和其他节点不太一样，区分开来
        //删除头节点
        while(head != null && head.val == val){
          head = head.next;
        } 
        //其余节点 头节点不能移动，将头节点赋值给当前节点
        ListNode cur = head;
        while(cur != null && cur.next != null){
            if(cur.next.val == val){
                //满足条件，当前节点next指向当前节点的next.next
                cur.next = cur.next.next;
            }else{
                //否则移动当前节点
                cur = cur.next;
            }
        }

        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

**第二种解法：**定义一个虚拟头节点，统一删除规则（设置一个虚拟头结点在进行删除操作。）

代码实现

public ListNode removeElements(ListNode head, int val) {
          if(head == null){
          return null;
          }  
           //统一规则，删除节点，定义一个虚拟头节点
           ListNode dummyHead = new ListNode(-1);
           dummyHead.next = head;

           //遍历链表  
           ListNode node = dummyHead;
           while(node.next != null){
               if(node.next.val == val){
                //当前节点的next指向当前节点的next.next
                node.next = node.next.next;
               }else{
               node = node.next;
               } 
           }

          return dummyHead.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4、设计链表

707.设计链表

力扣题目链接

题意：

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

思路：

定义两个节点，虚拟头节点和尾节点顺便记录一下链表中元素个数，上述任何操作都需要维护好这两个节点。

代码实现：

class MyLinkedList {

    /**
     * 虚拟头节点，能够统一操作，不需要区分是否是头节点
     */
    MyNode dummyHead;

    /**
     * 尾节点
     */
    MyNode tail;

    /**
     * 记录链表中元素个数
     */
    int count;

    static class MyNode {
        int val;
        MyNode next;

        public MyNode(int val) {
            this.val = val;
        }
    }

    public MyLinkedList() {
        //初始化虚拟头节点
        dummyHead = new MyNode(-1);
        count = 0;
    }

    public int get(int index) {
        if (index < 0 || index > count - 1) {
            return -1;
        }
        return getNode(index).val;
    }

    /**
     * 头插
     */
    public void addAtHead(int val) {
        MyNode cur = dummyHead;
        MyNode node = new MyNode(val);
        //除虚拟头节点无其他节点
        if (cur.next == null) {
            cur.next = node;
            tail = node;
        } else {
            //记录真正头节点
            MyNode next = cur.next;
            cur.next = node;
            node.next = next;
        }
        count++;
    }

    /**
     * 尾接
     */
    public void addAtTail(int val) {
        MyNode cur = dummyHead;
        MyNode node = new MyNode(val);
        if (tail == null) {
            cur.next = node;
        } else {
            tail.next = node;
        }
        tail = node;
        count++;
    }

    public void addAtIndex(int index, int val) {
        if (index <= 0) {
            addAtHead(val);
            return;
        }
        if (index == count) {
            addAtTail(val);
            return;
        }
        if (index > count) {
            // do nothing
            return;
        }
        MyNode prev = getNode(index - 1);
        MyNode cur = getNode(index);
        MyNode target = new MyNode(val);
        prev.next = target;
        target.next = cur;
        count++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index > count - 1) {
            return;
        }
        //删除头节点
        if (index == 0) {
            dummyHead.next = dummyHead.next.next;
        }
        //删除尾节点
        else if (index == count - 1) {
            //前一个节点
            MyNode prev = getNode(index - 1);
            prev.next = null;
            tail = prev;
        } else {
            //前一个节点
            MyNode prev = getNode(index - 1);
            //当前节点
            MyNode cur = prev.next;
            //后一个节点
            prev.next = cur.next;
        }
        count--;
    }

    /**
     * 获取链表对应节点元素
     *
     * @param index 确保下标在合理范围内 [0, count - 1]，否则返回null
     * @return 节点元素
     */
    public MyNode getNode(int index) {
        MyNode ans = null;
        //从真实头节点开始遍历
        MyNode cur = dummyHead.next;
        for (int i = 0; i <= index; i++) {
            ans = cur;
            cur = cur.next;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

5、反转链表

206.反转链表

力扣题目链接

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路：

1、借助栈空间；2、双指针头插法

代码实现：

请见我的博客

6、两两交换链表中的节点

24. 两两交换链表中的节点

力扣题目链接

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路：

固定操作：定义一个虚拟头节点，虚拟头节点指向真实头节点。需要交换相邻两两节点，首先要保证有相邻两两节点，只需定义一个指针，该指针指向上述两个相邻节点的前一个节点，该指针就可以从我们定义的虚拟节点开始（这不就统一节点操作了嘛），循环结束条件就是该指针的后面两个节点都不为null，循环里面操作无非就是交换相邻节点位置，指针向后移动两位，注意一些操作细节就OK了。（也很好理解嘛，只有一个节点不需要交换操作）

代码实现：

  public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        //搞一个虚拟头节点
        ListNode dummyHead = new ListNode(-1);
        //虚拟头节点next指向真实头节点
        dummyHead.next = head;
        //从虚拟头节点开始遍历 指向需要交换两个节点的前一个节点
        ListNode prev = dummyHead;
        while (prev.next != null && prev.next.next != null) {
            ListNode cur = prev.next;
            ListNode next = cur.next;
            //记录第二个节点的下一个节点（操作细节）
            ListNode nextNext = next.next;
            //节点交换位置
            next.next = cur;
            cur.next = nextNext;
            prev.next = next;
            //向后移两位
            prev = prev.next.next;
        }

        return dummyHead.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

7、删除链表的倒数第N个节点

19.删除链表的倒数第N个节点

力扣题目链接

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

进阶：你能尝试使用一趟扫描实现吗？

示例 1：

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2：

输入：head = [1], n = 1 输出：[] 示例 3：

输入：head = [1,2], n = 1 输出：[1]

思路：

其实这道题核心就是找到待删除节点的上一个节点，然后删除待删除节点。正常最先想到的就是先遍历一遍链表，得到链表元素个数，然后再一次遍历找到待删除节点的上一个节点，最后开始删除操作。（这种方式时间复杂度确实也是O(n)，但是最差情况可能会完整遍历两次链表，为什么说最差呢，比如说删除链表倒数第一个节点，第一次遍历一定是完整遍历操作，第二次找到待删除节点上一个节点这种情况不也就相当于完整遍历链表了嘛，所以说最差可能会完整遍历两次链表）

代码如下：

    public ListNode removeNthFromEnd(ListNode head, int n) {·
        if (head == null) {
            return null;
        }
        // 最坏要遍历两次链表
        // 第一次遍历获取链表长度，第二次遍历获取待删除节点前一个节点
        // 然后删除待删除节点
        ListNode cur = head;
        //链表节点个数
        int length = 0;
        while (cur != null) {
            length++;
            cur = cur.next;
        }

        int index = length - n;
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        //记录目标节点前一个节点
        cur = dummyHead;
        for (int i = 0; i < index ; i++) {
             cur = cur.next;
        }
        //删除待删除节点
        cur.next = cur.next.next;
        return dummyHead.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

那么如何完整遍历一次链表来解决该问题呢。快慢双指针：定义两个指针fast、slow，先让快指针指向链表 n + 1位置节点，然后再一次遍历快慢指针同时移动，当快指针遍历完链表结束循环，此时slow慢指针指向length - (n + 1) 位置（length是链表长度）就是链表待删除节点的上一个节点，找到之后删除即可。（这种方法相当于只会完整遍历链表一次）

代码实现：

     public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
		// 快慢双指针 遍历链表一次
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        // fast + slow = 链表长度（length）
        // 首先指向 n + 1 位置节点
        ListNode fast = dummyHead;
        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }
        // 该指针记录待删除节点的前一个节点
        ListNode slow = dummyHead;
        // 当fast指针移动链表末尾，slow指针就指向待删除节点的前一个节点 length - (n + 1)
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        //删除待删除节点
        slow.next = slow.next.next;

        return dummyHead.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

8、链表相交

面试题 02.07. 链表相交

同：160.链表相交

力扣题目链接

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

思路：

两个链表交点节点的指针。 要注意的是，交点不是数值相等，而是指针相等。使用双指针法，两个指针分别遍历两个链表，分别遍历结束后，再指向另一个链表的头节点继续遍历，直到两节点相等遍历结束，相等节点就是我们所要的答案。

代码实现：

  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       if (headA == null || headB == null) {
            return null;
        }
      
       ListNode p = headA;
       ListNode q = headB;
       //两指针相遇，遍历结束
       while(p != q){
           //没有到尾节点继续向后移，否则指向另一个链表头节点继续遍历
           p = p != null? p.next : headB;
           q = q != null? q.next : headA;
       }
       return p;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

9、环形链表

142.环形链表II

力扣题目链接

题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

思路：

主要考察两知识点：

• 判断链表是否环
• 如果有环，如何找到这个环的入口

判断链表是否有环

可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。（即如果有环的话，就是在环内fast指针以移动一个节点的速度追赶slow指针，两指针一定会相遇）

可以看如下动画：（快慢双指针终会相遇）

如果有环，如何找到这个环的入口

假设从头结点到环形入口节点的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点节点数为y。 从相遇节点再到环形入口节点节点数为 z。 如图所示：

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (z + y)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

(x + y) * 2 = x + y + n (y + z)
1

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢？

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

动画如下：

那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。

其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

代码实现：

还有一种就是注释代码，这种方法需要借助额外空间，并且List自动扩容也会消耗过多的时间，不是最优解法。

public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }

        //借助额外空间
        // List list = new ArrayList<>();
        // ListNode cur = head;
        // while(cur != null){
        //     //成环
        //     if(list.contains(cur)){
        //         return cur;
        //     }
        //     list.add(cur);
        //     cur = cur.next;
        // }
        // //未成环
        // return null;

        //快慢双指针判断是否成环
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                //快慢指针环内相遇节点，fast节点重新赋值为头节点
                //此时两指针都移动一个节点，相遇节点就是环入口节点
                fast = head;
                while(fast != slow){
                 fast = fast.next;
                 slow = slow.next;
                }
                return fast;
            }
        }

    	//未相遇，即链表不成环
        return null;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

10、总结：

操作类

解决此类问题，无非就是找到相应的节点、修改指针指向。通用做法就是创建一个虚拟头节点，虚拟头节点指向真实头节点(dummyHead.next = head)，这样操作是为了统一原链表所有节点的操作；否则就要分情况头节点和非头节点。然后操作时注意临界条件即可。

【可能还要注意的就是不能影响原本链表遍历，有的时候需要将当前节点的下一个节点提前声明出来使之不被改变以正确遍历链表】

例如：下面反转链表操作

查询类

解决此类问题，一般情况下可以借助外部空间，但是这种情况空间复杂度都是O(n)；更优解法空间复杂度O(1)，使用双指针（快慢双指针），这种方式可能会更加节省时间。使用两个指针，根据题意找出一定规律实现代码解决问题。

链表总结：