題目說明

給定一個 list，裡面有 k 個 linkedlist，回傳一個排序好的 linked list

解題思路

與第 21 題 Merge two sorted lists相似，這題會需要寫一個 helper function ，將兩個 linked list 排序後合併

將 lists 內的元素兩兩合併後，將結果 assign 回給 lists
直到 lists 內的元素只剩下一個為止

過程如下:
原 lists = [[1,4,5],[1,3,4],[2,6],[3,5,9],[1,8,11]]
1. [[1,1,3,4,4,5],[2,3,5,6,9],[1,8,11]]
2. [[1,1,2,3,3,4,4,5,5,6,6,9],[1,8,11]]
3. [[1,1,1,2,3,3,4,4,5,5,6,6,8,9,11]]

程式碼

# 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: List[Optional[ListNode]]) -> Optional[ListNode]:
        # edge case
        if not lists or len(lists) == 0:
            return None

        while len(lists) > 1:
            mergedLists = []

            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i+1] if (i + 1) < len(lists) else None
                mergedLists.append(self.mergeList(l1, l2))
            lists = mergedLists
        return lists[0]

    def mergeList(self, l1, l2):
        dummy = ListNode(0)
        tail = dummy
        while l1 and l2:
            if l1.val > l2.val:
                tail.next = l2
                l2 = l2.next
            else:
                tail.next = l1
                l1 = l1.next
            tail = tail.next
        if l1:
            tail.next = l1
        if l2:
            tail.next = l2
        return dummy.next

其他討論

這題參考 NeetCode 的解題影片，應該還有 heap solution 的解法

參考資料

1. NeetCode(2020-08-22)。Merge K Sorted Lists - Leetcode 23 - Python。摘自 Youtube (2023-01-24)