合并K个有序链表

Leetcode Link: 23. 合并K个升序链表 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。

解法一

思路：（为什么不对？）新建一个list，把当前所有链表的cur节点的值放到一个list里进行比较，None了就更新flag，flag用来指示是不是所有的链表全都弄完了。

题解：

import numpy as np
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
 
        K = len(lists)
        dummy = ListNode()
        cur = dummy
 
        flag = list(np.ones([K,1]))
        curValue = []
        for i in range(K):
            if not lists[i]:
                curValue.append(lists[i].val)
            else:
                flag[i] = 0
                curValue.append(10^4+1)
        
        while(sum(flag)>0):
            minInd = curValue.index(min(curValue))
            cur.next = lists[minInd]
            if not lists[minInd].next:
                lists[minInd] = lists[minInd].next
                curValue[minInd] = lists[minInd].val
            else:
                flag[minInd] = 0
                curValue[minInd] = 10^4+1
        
        return dummy.next

解法二

思路：二分法加递归，这个有点类似于归并排序的思路，分成左右部分，然后合并

题解：

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        '''二分 + 递归'''
        if len(lists)==0:
            return None
        else:
            output = self.recurMergeK(lists)
            return output
 
    def recurMergeK(self, rlists):
        if len(rlists) == 1:
            return rlists[0] # 递归终止条件
        else:
            mid = len(rlists) // 2
            leftList = self.recurMergeK(rlists[:mid])
            rightList = self.recurMergeK(rlists[mid:])
            return self.merge(leftList, rightList)
            
    def merge(self,listA, listB):
        dummy = ListNode()
        cur = dummy
        while(listA and listB):
            if listA.val < listB.val:
                cur.next = listA
                listA = listA.next
                cur = cur.next
            else:
                cur.next = listB
                listB = listB.next
                cur = cur.next
        if listA:
            cur.next = listA
        if listB:
            cur.next = listB
        
        return dummy.next

Note

其实可以看出来，很大程度参考了归并排序的代码

解法三

思路：优先级队列，堆 #todo

题解：

启发和联系

面对数量多、且两个两个做也是同样思路的问题，就可以考虑使用二分加递归，主要是想好二分的点和递归终止的条件