Grizzly's daily
0%

单链表解题技巧(1)——合并有序链表

发表于 更新于 分类于
本文字数： 2.8k 阅读时长 ≈ 3 分钟

本文是关于单链表的合并问题，1.合并两个有序链表；2.合并k个有序链表（堆）。

涉及 leetcode 的 21. 合并两个有序链表和 23. 合并K个升序链表。

合并两个有序链表

题目1

首先来看题目21. 合并两个有序链表：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例1：

输入：l1 = [1,2,4], l2 = [1,3,4]

输出：[1,1,2,3,4,4]

示例2：

输入：l1 = [], l2 = [0]

输出：[0]

理解一下1

题目的大概意思就是：

  1. 将两个本身就有序（升序）的链表合并起来，得到一个新的链表依旧是有序的；
  2. 并且新的链表依旧使用原本链表中的结点，而不是创建新的结点。（也就是用next指针指来指去）。

基本的思路是：

  1. 首先创建一个链表头res来表示最终的链表；
  2. 然后分别使用两个指针指向链表l1和链表l2；
  3. 再比较l1和l2对应结点的值的大小，将小的结点连接到res中；
  4. l1和l2不断向后遍历，重复3，最后剩下没遍历完的就直接放在res后。

解题1

以上的思路忽略了一些细节（n，n-1，1，0等这些边界问题），这里我们在处理第一个结点（无前结点）的时候还是需要分类讨论的，所以根据数据结构的定义，引入所谓的头结点，这样第一个结点就和其他结点都一样了

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
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    // 头结点
    ListNode* dummy = new ListNode(-1);
    ListNode* p = dummy;
    ListNode* p1 = list1, *p2 = list2;
    // 谁的结点小就将谁接在链表 dummy 后
    while(p1 && p2){
        if(p1->val > p2->val){
            p->next = p2;
            p2 = p2->next;
        }
        else{
            p->next = p1;
            p1 = p1->next;
        }
        p = p->next;
    }
    // 跳出 while 循环的条件必然是至少一条链遍历结束了，那么剩下的一条的后续部分直接接在 dummy 中即可。
    if(p1)
        p->next = p1;
    if(p2)
        p->next = p2;
    // 题目需要返回的是没有头结点的，所以是 next。
    return dummy->next;
}

合并K个有序链表

题目2

同样先看一下题目23. 合并K个升序链表：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例1：

输入：lists = [ [1,4,5],[1,3,4],[2,6] ]

输出：[1,1,2,3,4,4,5,6]

示例2：

输入：lists = [ ]

输出：[ ]

理解一下2

就相当于之前是两个有序链表两两合并，现在是K个链表进行有序合并成一个有序链表。

基本的思路有两个：

两两合并2

第一种方法是在上一题的基础上，直接进行两两合并，得到有序链表，当然这里也有两种思路：一个是直接进行k-1次两两合并，另一个是使用归并两两合并，无非是时间换空间的问题（嗷，还有一个问题是归并我不熟练）。

这里提供我用第一个思路写的k-1次归并题解，其中mergeTwoLists函数就是之前的两两合并（好家伙，直接复制！）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* mergeKLists(vector<ListNode*>& lists) {
    // 无链表
    if(lists.size() == 0){
        return nullptr;
    }
    // 仅有一个链表
    if(lists.size() == 1){
        return lists[0];
    }
    // k-1 次两两合并
    ListNode * res = lists[0];
    for(int i = 1; i < lists.size(); i++){
        res = mergeTwoLists(res,lists[i]);
    }
    return res;
}

小根堆合并

第二种方法需要使用数据结构——小根堆（本质上是一棵完全二叉树），通过堆的性质进行合并，在很多外部排序的时候会采用这种方法，同样的也有两个思路：

  1. 一个是将所有的链表所有的结点都一次性扔到堆中（显然需要空间极大），然后依次从堆顶取出结点链接到链表dummy中即可；
  2. 另一个是以k个链表的头结点构建大小为k的小根堆，堆顶的的结点就是最小结点，将其拿出链接到链表dummy中即可，并将该链上的next结点加入小根堆，并进行调整，直至堆中无结点即可。

很明显小根堆合并比两两合并好多了，但是实际 coding 的时候其实并不一定能写出来（orz），所以这两种方法作为思路，并提供了一个labuladong的 java 题解。

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
ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    // 优先级队列，最小堆
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
    // 将 k 个链表的头结点加入最小堆
    for (ListNode head : lists) {
        if (head != null)
            pq.add(head);
    }
    while (!pq.isEmpty()) {
        // 获取最小节点，接到结果链表中
        ListNode node = pq.poll();
        p.next = node;
        if (node.next != null) {
            pq.add(node.next);
        }
        // p 指针不断前进
        p = p.next;
    }
    return dummy.next;
}

个人收获

这里主要学到的是对k个链表进行合并的思路：

  1. 两两合并的方法其实很常见，在ML中，对多分类问题也经常使用多次二分类进行实现，本质上感觉还是很相似的，好吧不是一回事，总之是将问题进行拆分，然后再一个一个解决，虽然暴力（O(NK)），但是起码能够解决问题，不至于完全写不出来。
  2. 对于小根堆其实也是比较熟悉了，在数据结构中小根堆的画图我可是熟悉的一塌糊涂（除了考试没啥用），但是代码上就显得比较不熟练了，之后在树的这一个模块中再好好练一练。这个可以很好的降低时间的复杂度，相应的付出一些时间，不过效果要比两两合并好多（O(Nlogk)）。
------ 本文结束------