InterviewBit – Merge K Sorted Lists

Source: Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list.

Example :

1 -> 10 -> 20
4 -> 11 -> 13
3 -> 8 -> 9

will result in

1 -> 3 -> 4 -> 8 -> 9 -> 10 -> 11 -> 13 -> 20

---

解題：

因為這題被分類在 Heaps and Maps 項下，理論上似乎是用 Heapsort 來解比較好，但筆者在寫題目時考量到對於連結串列 linked list 如要使用該方法須先使用額外的記憶體將所有 linked list 的值存出後再執行 sorting，似乎在速度上不見得會比較快。故筆者這題是用近似 divide and conquer 的方式，將個別 linked list 兩兩一組合併後先存進另一組陣列，等一整輪結束後再用相同方法合併，直到只剩下一個整合完成的 linked list 來執行輸出。最後沒發生TLE，那就不管它啦！

Code:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param lst: list of linked list
    # @return the head node in the linked list
    def mergeKLists(self, lst):
        tempMerger = []
        while len(lst) + len(tempMerger) > 1:
            while len(lst) > 1:
                linklst1, linklst2 = lst.pop(), lst.pop()
                tempMerger.append(self.merger(linklst1, linklst2))
            while len(tempMerger) > 1:
                linklst1, linklst2 = tempMerger.pop(), tempMerger.pop()
                lst.append(self.merger(linklst1, linklst2))
            if lst:
                tempMerger.append(lst.pop())
        if lst:
            return lst.pop()
        return tempMerger.pop()
    
    def merger(self, linklst1, linklst2):
        curr1, curr2 = linklst1, linklst2
        if curr1.val > curr2.val:
            root = curr2
            curr2 = curr2.next
        else:
            root = curr1
            curr1 = curr1.next
        
        temp = root
        while curr1 and curr2:
            if curr1.val > curr2.val:
                temp.next = curr2
                curr2 = curr2.next
            else:
                temp.next = curr1
                curr1 = curr1.next
            temp = temp.next
        if curr1:
            temp.next = curr1
        else:
            temp.next = curr2
        return root

GitHub: GitHub