合并K个排序链表

发表于 | 分类于 | 阅读次数：
本文字数： 3.3k | 阅读时长 ≈ 8 分钟

问题提出

#23 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。

示例:

1
2
3
4
5
6
7
8
> 输入:
> [
>   1->4->5,
>   1->3->4,
>   2->6
> ]
> 输出: 1->1->2->3->4->4->5->6
>

解题思路

k=2？

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

示例：

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

合并两个有序链表比较简单，每次取出链表头，将较小的加入到新链表中，并将这个较小的项从原链表中删除。重复这个过程，直到其中一个链表为空。这时再将那个非空的链表加到新链表的末尾即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy = ListNode(0);
    ListNode *ret = &dummy;
    ListNode *cur = ret;
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            cur->next = l1;
            cur = cur->next;
            l1 = l1->next;
        } else {
            cur->next = l2;
            cur = cur->next;
            l2 = l2->next;
        }
    }
    if (l1 != NULL) cur->next = l1;
    if (l2 != NULL) cur->next = l2;
    return ret->next;
}

k为任意值

借鉴上述k=2的思路，算法步骤如下：

  1. 初始化：取出每个链表的第一个元素，将其排序，排序结果记录在table:vector<int>中。table中记录的并不是链表中的元素，而是链表的序号，因此table中的值为1~k的一个排列
  2. 设x为table中第一个元素对应的那个链表，如果x为空，算法结束；如果x非空，取出x中的第一个元素，将其加到新链表中，并将其从x中删除
  3. 更新table：同样设x为table中第一个元素对应的那个链表
    1. 将table中的第一个元素删除
    2. 步骤2中刚刚删除了x的第一个元素，如果此时x为空，将x的序号加到table的末尾；如果x非空，根据x中第一个元素的大小将x的序号插入到table中合适的位置
  4. 返回步骤2

细节优化

考虑k=0或者传入的有些链表为空的情况，需要在执行上述算法之前进行预处理：删除空链表，删除后如果k=0则直接返回NULL

这里记录一下删除 vector中特定元素的方法：

1
2
3
4
for (auto it = vec.begin(); it != vec.end();) {
    if (*it == ITEM_TO_BE_DELETED) it = vec.erase(it);
    else it++;
}

代码

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
ListNode* mergeKLists(vector<ListNode*>& lists) {
	// delete NULL items
	for (auto it = lists.begin(); it != lists.end();) {
		if (*it == NULL) it = lists.erase(it);
		else it++;
	}
	// if lists is void, return directly
	if (lists.size() == 0) { return NULL; }

	vector<int> table;
	ListNode *ret;
	ListNode dummy = ListNode(0);
	ret = &dummy;

	init(table, lists);

	ListNode *cur = ret;
	while (true) {
		int index = table[0];
		if (lists[index] == NULL) 
			break;

		cur->next = lists[index];
		cur = cur->next;
		lists[index] = lists[index]->next;
		update(table, lists);
	}

	return ret->next;
}


void init(vector<int> &table, vector<ListNode*> &lists) {
	int k = lists.size();
	vector<int> temp;
	for (int i = 0; i < k; i++) {
		temp.push_back(lists[i]->val);
		table.push_back(i);
	}

	for (int i = 0; i < k - 1; i++) {
		for (int j = i + 1; j < k; j++) {
			if (temp[i] > temp[j]) {
				swap(temp[i], temp[j]);
				swap(table[i], table[j]);
			}
		}
	}
}

void update(vector<int> &table, vector<ListNode*> &lists) {
	int focus = table[0];
	table.erase(table.begin());
	if (lists[focus] == NULL) {
		table.insert(table.end(), focus);
		return;
	}

	int value = lists[focus]->val;
	for (auto it = table.begin(); it < table.end(); it++) {
		if (lists[*it] == NULL || value < lists[*it]->val) {
			table.insert(it, focus);
			return;
		}
	}
	table.insert(table.end(), focus);
}