合并链表

Posted on | In

虽然有序链表的合并做起来不复杂，但是每次做一次我就有不同的感受。
下面给出两个合并有序链表的题目,一道easy和一道hard.

21. 合并两个有序链表

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

示例：

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

思想: 迭代的想法我就不赘述了,这里主要是写下递归的解法.

关于递归的解法我下面给出个链接, 链接给出的ppt很好的说明了链表是如何用递归实现合并的.

腐烂的橘子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1)    return l2;
        if (!l2)    return l1;
        // 由于l1节点值小于l2的节点值
        // l1节点被选出来作为前置节点然后递归的去找后继节点 
        if (l1->val < l2->val) 
            l1->next = mergeTwoLists(l1->next, l2);
        else
            l2->next = mergeTwoLists(l1, l2->next);
        return l1->val < l2->val ? l1 : l2;
    }
};

23. 合并K个升序链表

*思路1: * 用priority_queue每次找到当前节点中最小值

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
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())  return nullptr;
        // 小顶堆是 greater ==> >
        auto cmp = [](ListNode* A, ListNode* B){
            return A->val > B->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        // 先将所有非空链表的首节点push进小顶堆
        for (auto l : lists)
            if (l)  pq.push(l);
        ListNode* dummy_head = new ListNode(-1);
        ListNode* tail = dummy_head;
        while(!pq.empty()){
            tail->next = pq.top();
            pq.pop();
            tail = tail->next;
            // 若某个链表已经遍历完了,就跳出循环
            if (!tail->next)    continue; 
            else
                pq.push(tail->next);
            // 将当前所得链断开
            tail->next = nullptr;
        }
        return dummy_head->next;
    }
};

思路2: 用上述的归并,只不过每次归并所得的链表再与剩下的链表继续归并.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())  return nullptr;
        for (int i = 1; i < lists.size(); ++i)
            lists[0] = mergeKLists(lists[0], lists[i]);
        return lists[0];
    }
    ListNode* mergeKLists(ListNode* l1, ListNode* l2){
        if (!l1)    return l2;
        if (!l2)    return l1;
        if (l1->val < l2->val)  l1->next = mergeKLists(l1->next, l2);
        else    l2->next = mergeKLists(l1, l2->next);
        return l1->val < l2->val ? l1 : l2;
    }
};