LeetCode: 23. Merge k Sorted Lists

题目

原题地址：https://leetcode.com/problems/merge-k-sorted-lists/

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length won't exceed 10^4.

解法

从头到尾挨个合并数组内的链表

思路如下：

  1. 取第一个链表作为新的链表
  2. 然后遍历数组，将数组元素跟新链表合并得到合并后的新链表（合并两个链表的详细说明详见前面的 LeetCode: 21. Merge Two Sorted Lists ）
  3. 然后再用合并后的新链表跟下一个链表合并
  4. 数组遍历完成后就得到了一个合并了所有链表的新链表

这个方法的 Python 代码类似下面这样:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        if not lists:
            return None

        new_list = None
        for list in lists:
            new_list = self.mergeTwoLists(new_list, list)

        return new_list

    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1

        dummy = ListNode()
        tail = dummy

        while l1 is not None and l2 is not None:
            if l1.val <= l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next

            tail = tail.next

            if l1 is None:
                tail.next = l2
            if l2 is None:
                tail.next = l1

        return dummy.next

使用首尾合并的方法加速合并

上面的挨个合并的方法可以通过改为首尾合并的方法来加速合并：

  1. 两个指针，i 指向数组第一个元素，j 指向数组最后一个元素
  2. 合并两个指针对应的链表，将合并后的结果保存到左边指针的数组索引位置
  3. 相向移动两个指针，每移动一步就按上面的方法合并链表并保存结果
  4. 当两个指针相遇时(i >= j 时, 数组元素个数为奇数是 i == j, 数组元素个数为偶数是 i - 1 == j)，将 i 移到数组第一个元素，继续按上面的方法首尾合并 i、j 处的链表
  5. 当 i == j == 0 时，合并结束，此时数组的第一个元素的值即为完成合并后的新链表

这个方法的 Python 代码类似下面这样:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists):
        if not lists:
            return None

        i = 0
        j = len(lists) - 1
        while i < j:
            new_list = self.mergeTwoLists(lists[i], lists[j])
            lists[i] = new_list
            i += 1
            j -= 1
            if i >= j:
                i = 0

        return lists[0]


    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1

        dummy = ListNode()
        tail = dummy

        while l1 is not None and l2 is not None:
            if l1.val <= l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next

            tail = tail.next

            if l1 is None:
                tail.next = l2
            if l2 is None:
                tail.next = l1

        return dummy.next

Comments