链表

作者：画手大鹏
链接：https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz1ooc/
来源：力扣（LeetCode）

1
2
3

# 剑指 Offer 18. 删除链表的节点

题目描述

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

1
2
3

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

1
2
3

说明：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

思路

标签：链表遍历
整体思路是使用挨着的前后 2 个指针，当前方指针遇到要删除的值时，则使用后方指针重新构造连接并跳过该值
- 首先判断头指针是否为 null，如果为空则直接返回 null
- 如果头指针 head.val 即为要删除的值，则直接返回 head.next 即可
- 初始化前指针 pre 和后指针 post，两个指针紧挨着，距离为 1
- 前后指针一直遍历链表，直到遍历到链表结尾或等于要删除的值时则跳出循环
- 如果找到要删除的值，则令 post.next = pre.next，相当于将链表中的值删除
- 时间复杂度：O(n)，空间复杂度：O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        // 首先判断头指针是否为 null，如果为空则直接返回 null
        if(head == null) {
            return null;
        }
        
        // 如果头指针 head.val 即为要删除的值，则直接返回 head.next 即可
        if(head.val == val) {
            return head.next;
        }
        
        // 初始化前指针 pre 和后指针 post，两个指针紧挨着，距离为 1
        ListNode left = head;
        ListNode right = head.next;
        
        // 前后指针一直遍历链表，直到遍历到链表结尾或等于要删除的值时则跳出循环
        while(right != null && right.val != val) {
            left = right;
            right = right.next;
        }
        
        // 如果找到要删除的值，则令 post.next = pre.next，相当于将链表中的值删除
        if(right != null) {
            left.next = right.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
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 剑指 Offer 22. 链表中倒数第 k 个节点

题目描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

1
2
3

思路

标签：链表遍历
整体思路是使用双指针，间隔 k 个位置，同时向后移动，当前方指针移动到尾部时，后方指针的位置就是倒数第 k 个数字
- 首先构建前指针 pre，后指针 post
- 前指针 pre 向前移动 k 个位置
- 前指针 pre 和后指针 post 同时向前移动，直到前指针为 null 时停止
- 后指针 post 即为倒数第 k 个数字
时间复杂度：O(n)，空间复杂度：O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode pre = head;
        ListNode post = head;
        
        // 前指针 pre 向前移动 k 个位置
        for(int i = 0; i < k; i++) {
            pre = pre.next;
        }
        
        // 前指针 pre 和后指针 post 同时向前移动，直到前指针为 null 时停止
        while(pre != null) {
            pre = pre.next;
            post = post.next;
        }
        
        // 后指针 post 即为倒数第 k 个数字
        return post;
    }
}

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

# 剑指 Offer 24. 反转链表

题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

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

1
2

限制：

0 <= 节点个数 <= 5000

**思路**

标签：链表遍历
整体思路：通过前指针、当前指针和临时指针进行位置交换，从头部开始 2 个节点为一组进行倒序交换，直到遍历到链表结尾将链表反转完成
时间复杂度：O(n)，空间复杂度：O(1)

算法流程

初始化当前指针 cur = null，前指针 pre = head
当 pre != null 时，说明还未到达链表结尾，则不断进行遍历交换
tmp = pre.next，保存下一次要进行倒转的指针位置
pre.next = cur，实现链表中 2 个节点的反转
cur = pre，cur 指针后移一个位置
pre = tmp，pre 指针后移一个位置
进行下一轮的倒转，直到结束时最终的链表头结点为 cur，返回 cur 即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode left = null;
        ListNode right = head;
        
        // 当 right != null 时，说明还未到达链表结尾，则不断进行遍历交换
        while (right != null) {       
            ListNode tmp = right.next; 	// 保存下一次要进行倒转的指针位置
            right.next = left;     		// 实现链表中 2 个节点的反转
            left = right;				// left  指针后移一个位置
            right = tmp;				// right 指针后移一个位置
        }
        
        // 最终的链表头结点为 cur，返回 cur 即可
        return left;
    }
}

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

# 剑指 Offer 25. 合并两个排序的链表

题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例 1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

1
2

限制：

0 <= 链表长度 <= 1000

思路

标签：链表、递归
这道题可以使用递归实现，新链表也不需要构造新节点
终止条件：两条链表分别名为 l1 和 l2，当 l1 为空或 l2 为空时结束
返回值：每一层调用都返回排序好的链表头
本级递归内容：如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理
O(m+n)，mm 为 l1 的长度，nn 为 l2 的长度

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }

        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

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

迭代：

首先我们需要一个变量 head 来保存合并之后链表的头部，你可以把 head 设置为一个虚拟的头（也就是 head 的 val 属性不保存任何值），这是为了方便代码的书写，在整个链表合并完之后，返回它的下一位置即可。
我们需要一个指针 tail 来记录下一个插入位置的前一个位置，以及两个指针 aPtr 和 bPtr 来记录 aa 和 bb 未合并部分的第一位。注意这里的描述，tail 不是下一个插入的位置，aPtr 和 bPtr 所指向的元素处于「待合并」的状态，也就是说它们还没有合并入最终的链表。当然你也可以给他们赋予其他的定义，但是定义不同实现就会不同。
当 aPtr 和 bPtr 都不为空的时候，取 val 熟悉较小的合并；如果 aPtr 为空，则把整个 bPtr 以及后面的元素全部合并；bPtr 为空时同理。
在合并的时候，应该先调整 tail 的 next 属性，再后移 tail 和 *Ptr（aPtr 或者 bPtr）。那么这里 tail 和 *Ptr 是否存在先后顺序呢？它们谁先动谁后动都是一样的，不会改变任何元素的 next 指针。

public ListNode mergeTwoLists(ListNode a, ListNode b) {
    if (a == null || b == null) {
        return a != null ? a : b;
    }
    ListNode head = new ListNode(0);
    ListNode tail = head, aPtr = a, bPtr = b;
    while (aPtr != null && bPtr != null) {
        if (aPtr.val < bPtr.val) {
            tail.next = aPtr;
            aPtr = aPtr.next;
        } else {
            tail.next = bPtr;
            bPtr = bPtr.next;
        }
        tail = tail.next;
    }
    tail.next = (aPtr != null ? aPtr : bPtr);
    return head.next;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 剑指 Offer 52. 两个链表的第一个公共节点

题目描述

输入两个链表，找出它们的第一个公共节点。

注意：

如果两个链表没有交点，返回 null。
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路

标签：双指针链表遍历
分别构造 2 个指针去遍历 2 个链表，无论哪个指针到尾部时，让其重新回到对方的头部，最终会在第一个公共节点相遇，如果没有，则会在 null 处相遇
时间复杂度：设 A 链表非公共长度为 m，B 链表非公共长度为 n，公共部分为 b，则复杂度为 O(m+n+b)，空间复杂度：O(1)

算法流程

使用 headA 和 headB 初始化 2 个指针 curA 和 curB，用来遍历使用
进行循环遍历，直到 curA 和 curB 相同时结束
遍历过程中如果 curA 到尾部则将其重新放回头部 headB，如果 curB 到尾部则将其重新放回头部 headA
循环结束时在第一个公共节点相遇，返回该节点 curA

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 用来遍历
        ListNode curA = headA;
        ListNode curB = headB;

        // 进行循环遍历，直到 curA 和 curB 相同时结束
        while (curA != curB) {
            // 遍历过程中如果 curA 到尾部则将其重新放回头部 headB，如果 curB 到尾部则将其重新放回头部 headA
            curA = curA != null ? curA.next : headB;
            curB = curB != null ? curB.next : headA;
        }
        
        // 循环结束时在第一个公共节点相遇，返回该节点 curA
        return curA;
    }
}

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

这个类似于将两个长短不一的片段拼接一下，类似于
abcijk
epijk

分别拼接对方之后
abcijkepijk
epijkabcijk
长度一样了，尾部当然也就一样了

1
2
3
4
5
6
7
8

# 第83题，删除排序链表中的重复元素 II

问题描述

难度：简单
存在一个按升序排列的链表，给你这个链表的头节点head，请你删除所有重复的元素，使每个元素只出现一次。
返回同样按升序排列的结果链表。

示例 1：

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

1
2

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

使用一个指针解决

这题说了链表中的值是按照升序排列的，既然是排过序的，那么相同的节点肯定是挨着的。
我们可以使用一个指针cur，每次都要判断是否和他后面的节点值相同，如果相同就把后面的那个节点给删除。

public ListNode deleteDuplicates(ListNode head) {
    //如果但前节点是空，或者是单个节点，直接返回
    if (head == null || head.next == null)
        return head;
    
    //只用一个指针cur指向当前节点
    ListNode cur = head;
    
    while (cur.next != null) {
        //如果当前节点的值和下一个节点的值相同，
        //就把下一个节点值给删除
        if (cur.val == cur.next.val) {
            cur.next = cur.next.next;
        } else {
            //否则cur就往后移一步
            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

递归方式解决

除了上面使用一个指针以外，我们还可以使用递归的方式来解决。
这个需要对链表的逆序访问比较熟悉，关于链表的逆序访问也可以看下1，倒叙打印链表。

public ListNode deleteDuplicates(ListNode head) {
    //递归的边界条件判断
    if (head == null || head.next == null)
        return head;
    
    //递归，相当于从后往前遍历
    head.next = deleteDuplicates(head.next);
    
    //如果当前节点和下一个一样，直接返回下一个节点，否则
    //返回当前节点
    return head.val == head.next.val ? head.next : head;
}

1
2
3
4
5
6
7
8
9
10
11
12

# 第82题，删除排序链表中的重复元素

难度：中等
存在一个按升序排列的链表，给你这个链表的头节点head，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。返回同样按升序排列的结果链表。

示例 1：

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

1
2

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

双指针解决

这题的解决思路就是使用两个指针，一个指针cur指向当前节点，一个指针pre指向当前节点cur的前一个节点。
cur始终和他的下一个节点比较，如果相同就往后移，如果不相同我们就需要判断pre的下一个节点是否是cur，如果是cur说明没有相同的节点，如果不是cur说明有相同的节点，我们就要删除

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null)
        return head;
    //添加一个dummy节点
    ListNode dummy = new ListNode(0);
    //让dummy节点的next指针指向head。
    dummy.next = head;
    //指向当前遍历的节点
    ListNode cur = head;
    //指向当前节点pre的前一个节点
    ListNode pre = dummy;
    while (cur != null) {
        while (cur.next != null && cur.val == cur.next.val) {
            //如果有重复的，cur就一直往下走
            cur = cur.next;
        }
        //判断上面有没有重复的节点，如果pre.next == cur，说明没有
        //重复的节点。否则说明有重复的节点，然后还要把重复的节点给删除
        if (pre.next == cur) {
            pre = pre.next;
        } else {
            //有重复的就删除
            pre.next = cur.next;
        }
        cur = cur.next;
    }
    return dummy.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
28

# 23. 合并K个升序链表 (opens new window)

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

1
2
3
4
5
6
7
8
9
10

示例 2：

输入：lists = []
输出：[]

1
2

示例 3：

输入：lists = [[]]
输出：[]

1
2

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[I] [j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

方法一：顺序合并

我们可以想到一种最朴素的方法：用一个变量 ans 来维护以及合并的链表，第 i 次循环把第 i 个链表和 ans 合并，答案保存到 ans 中。
时间复杂度为。
空间复杂度：没有用到与 k 和 n 规模相关的辅助空间，故渐进空间复杂度为 O(1)。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.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
28
29

方法二：分治合并

考虑优化方法一，用分治的方法进行合并。
将 k 个链表配对并将同一对中的链表合并；
第一轮合并以后， k 个链表被合并成了个链表，平均长度为，然后是个链表等等；
重复这一过程，直到我们得到了最终的有序链表。

时间复杂度为。
空间复杂度：递归会使用到空间代价的栈空间。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r)
            return lists[l];
        
        int mid = l + (r - l) / 2;
        
        ListNode l1 = merge(lists, l, mid);
        ListNode l2 = merge(lists, mid + 1, r);
        return mergeTwoLists(l1, l2);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

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

方法三：使用优先队列合并

这个方法和前两种方法的思路有所不同
我们需要维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元，
每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。
复杂度分析
- 时间复杂度：考虑优先队列中的元素不超过 k 个，那么插入和删除的时间代价为，这里最多有 kn 个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为。
- 空间复杂度：这里用了优先队列，优先队列中的元素不超过 k 个，故渐进空间复杂度为。

class Solution {
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(Status status2) {
            return this.val - status2.val;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<Status>();

    public ListNode mergeKLists(ListNode[] lists) {
        for (ListNode node: lists) {
            if (node != null) {
                queue.offer(new Status(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }
}

// or 
class Solution {
   public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                if (o1.val < o2.val) return -1;
                else if (o1.val == o2.val) return 0;
                else return 1;
            }
        });
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        for (ListNode node : lists) {
            if (node != null) queue.add(node);
        }
        while (!queue.isEmpty()) {
            p.next = queue.poll();
            p = p.next;
            if (p.next != null) queue.add(p.next);
        }
        return dummy.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
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

上次更新: 2021/12/24, 09:59:48

← 栈与列堆 DFS and BFS→