LeetCode#23. Merge k Sorted Lists

发表于 | 分类于 ， ，

这是一道hard的题目，在此之前，先看与之类似的easy的题目：

LeetCode#21 Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1
2
Input: 1->2->4, 1->3->4
Output: 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
20
21
22
23
24
25
/**
 * Struct ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
ListNode mergeTwoLists(l1, l2)  // l1/l2分别是两个链表的当前节点
  if (l1 = null)
    return l2

  if (l2 = null)
    return l1

  // 通过递归拼接链表
  // 两个链表的当前节点小的要不就是合并后的头结点，
  // 要不就已经拼接到之前的节点中，所以只需将小节点的next与大节点对比
  // 就可以得到当前小节点的下一个节点，以此类推就可以合并两条链表。
  // 因此使用递归就可以解决这个问题。
  if (l1.val < l2.val)
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  else
    l2.next = mergeTwoLists(l1, l2.next)
    return l2

LeetCode#23 Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

1
2
3
4
5
6
7
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

上一道题是合并两个链表，这道题是合并k个链表。如果逐个合并的话，每个链表的节点要访问k次，那么时间复杂度会达到O(n2)，这个思路会超时，需要换一种方式来完成。

如果熟悉归并排序的话，很容易就能想到，将多个一排序的链表合并在一起，不就是跟归并排序的合并过程一致吗？而我们知道，归并排序的每个节点只会访问log2n。如下图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
=====  =====  =====  =====
| 1 |  | 3 |  | 2 |  | 4 |
=====  =====  =====  =====
  |      |      |      |
  └──────┘      └──────┘
      |             |
  =========     =========
  | 1 | 3 |     | 2 | 4 |
  =========     =========
      |             |
      └─────────────┘
              |
      =================
      | 1 | 2 | 3 | 4 |
      =================

可以看到，以1为例，它只与2和3分别对比了一次，对比次数是2（log2n）。虽然3的比较次数多于2，但是4的对比次数又少于2，其平均值仍是2。实际上，不管n有多大，每一个数的平均访问次数都是log2n。因此，将k个链表两两合并，再两两合并，直到只剩下一个链表，这个链表就是答案。

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(lists)  // lists是一个数组，包含所有要合并的链表
  size = lists.length
  if (size = 0)
    reutrn null

  while (size > 1)
    for (i = 0; i < size; i++)
      first = i << 1
      second = i + 1
      if (first < size && second < size)
        l1 = lists[first]                // l1是第一个链表的头结点
        l2 = lists[second]               // l2是第二个链表的头结点
        lists[i] = mergeTwoLists(l1, l2) // 合并两个链表，并放到数组中
      else
        // 如果只有单数个链表，那最后一个暂不需合并
        if (first < size)
          lists[i] = lists[first]
          size = i + 1
        else
          size = i

        break

  // 剩下的第一个链表就是答案
  return lists[0]