7

LeetCode: 23. Merge k Sorted Lists

 3 years ago
source link: https://mozillazg.com/2020/10/leetcode-23-merge-k-sorted-lists.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目

原题地址：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

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK