leetcode 合并k个排序列表（三种解法）

深碍√TFBOYSˉ_ 2022-03-27 08:37 132阅读 0赞

**题目描述**  
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。  
![在这里插入图片描述][20190112202413929.png]

--------------------

### 解法1 ###

建立一个数组，将所有元素保存，排序之后，再链接成一个链表

class Solution:
       def mergeKLists(self, lists):
            """ :type lists: List[ListNode] :rtype: ListNode """
            
            #遍历链表，将所有链表的所有元素放到一个数组里面
            nodeList = []
            for i in range(len(lists)):
                currentNode = lists[i]
                #遍历某个链表
                while(currentNode):
                    nodeList.append(currentNode)
                    currentNode = currentNode.next
                    
            #根据node的val对数组进行排序 
            nodeList = sorted(nodeList,key = lambda x:x.val)
            
            #对排序好的数组的元素，一个个地连接成新的链表（这里的tempHead是为了方便设置的头节点）
            tempHead = ListNode(0)
            currentNode = tempHead
            for i in range(len(nodeList)):
                currentNode.next = nodeList[i]
                currentNode = currentNode.next
                
            return tempHead.next

![在这里插入图片描述][20190112202721231.png]

--------------------

### 解法2 ###

对lists里面的链表两两合并，知道lists里面只有一个元素

class Solution:
        def mergeTowLists(self, list1, list2):
            head = None
            if list1 == None and list2 == None:
                return None
            if list1 == None:
                return list2
            if list2 == None:
                return list1
            if list1.val <= list2.val:
                head = list1
                head.next = self.mergeTowLists(list1.next, list2)
            else:
                head = list2
                head.next = self.mergeTowLists(list, list2.next)
            return head
        def mergeKLists(self, lists):
            """ :type lists: List[ListNode] :rtype: ListNode """
            if lists == []:
                return None
            while len(lists) > 1:
                list1 = lists.pop()
                list2 = lists.pop()
                lists.append(self.mergeTowLists(list1, list2))
            return lists[0]

这种解法是超时的：  
![在这里插入图片描述][20190112202916190.png]

--------------------

### 解法3 ###

还是使用两两排序的方式，不过采用分治法的思想。  
定义一个partition函数，进行二分归并。  
注意partition函数的写法

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    class Solution:
        def mergeTowLists(self, list1, list2):
            head = None
            if list1 == None and list2 == None:
                return None
            if list1 == None:
                return list2
            if list2 == None:
                return list1
            if list1.val <= list2.val:
                head = list1
                head.next = self.mergeTowLists(list1.next, list2)
            else:
                head = list2
                head.next = self.mergeTowLists(list1, list2.next)
            return head
        def partition(self, lists, start, end):
            if start == end:
                return lists[start]
            if start < end:
                mid = (start + end) // 2
                l1 = self.partition(lists, start, mid)
                l2 = self.partition(lists, mid + 1, end)
                return self.mergeTowLists(l1, l2)
        def mergeKLists(self, lists):
            """ :type lists: List[ListNode] :rtype: ListNode """
            if lists == []:
                return None
            return self.partition(lists, 0, len(lists) - 1)

![在这里插入图片描述][20190112203116935.png]  
这种方法的效率要比第一种方法小点

[20190112202413929.png]: /images/20220327/06a001c41b524c1b90db69992ad9faf1.png
[20190112202721231.png]: /images/20220327/8763de96005c459d8e52c5646fec47d6.png
[20190112202916190.png]: /images/20220327/31bc3b841e434303ab5a57358966f068.png
[20190112203116935.png]: /images/20220327/d16b72c936894aca8b93da15a8adbb6f.png