T23 合并K个升序链表

桌桌 2022-8-12 60 8/12

题目描述如下:

T23 合并K个升序链表

解题思路:每次从这几个链表中选择一个最小的值,加入到head值指向的合并链表的链表尾部,选择完毕就令当前被选择的结点(在被选择的升序链表中)指向下一个next结点,并进行下一轮的比较。如果其中有一个升序链表先被选完了,就将该None值pop掉,直到所有的升序链表都被选择完毕且被pop掉时,就得到了合并后的链表结果。

代码如下:

# 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]:
        k = len(lists)
        listp = [lists[i] for i in range(k)]
        head = None
        pnode_pre = None

        #排除掉空列表的情况
        for i in range(k-1,-1,-1):
            if listp[i] is None:
                listp.pop(i)

        # 还有结点可以选择的话
        while listp!=[]:
            # 找到当前listp中存在的最小的值和下标,并且移动到选择完的下一个
            minval = listp[0].val
            index = 0
            for i in range(1,len(listp)):
                if minval > listp[i].val:
                    minval = listp[i].val
                    index = i
            if listp[index].next is None:
                listp.pop(index)
            else:
                listp[index] = listp[index].next
            
            # 前一个结点指向新建的节点
            node = ListNode(minval, None)
            if head is None: 
                head = node
                pnode_pre = node
            else:
                pnode_pre.next = node
                pnode_pre = node

        return head

结果如下:

T23 合并K个升序链表

看到结果发现是真的慢,想了想发现有很多可以优化的地方:

空间复杂度上:

首先不需要使用listp来进行存储,题目中给的就是listp列表的作用

同时,也不需要再次建立一个Linknode对象,直接使用输入中链接的就可以。

试了一下:

# 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]:
        k = len(lists)
        head = None
        pnode_pre = None

        #排除掉空列表的情况
        for i in range(k-1,-1,-1):
            if lists[i] is None:
                lists.pop(i)
                
        # 还有结点可以选择的话
        while lists!=[]:
            # 找到当前listp中存在的最小的值和下标,并且移动到选择完的下一个
            minval = lists[0].val
            index = 0
            for i in range(1,len(lists)):
                if minval > lists[i].val:
                    minval = lists[i].val
                    index = i
            if lists[index].next is None:
                node = lists.pop(index)
            else:
                node = lists[index]
                lists[index] = lists[index].next          
            # 前一个结点指向新建的节点
            if head is None: 
                head = node
                pnode_pre = node
            else:
                pnode_pre.next = node
                pnode_pre = node

        return head

结果空间复杂度降下去了:

T23 合并K个升序链表

时间复杂度上,应该要减少比较的次数,如果每次都需要从k个结点中选择一个最小的,确实难以减少比较次数,所以想着做类似于合并排序算法,两个两个一组排序再合并。

转念一想,最后要的是所有值的最终的排序,那我直接把所有值得到后再排序岂不是更快?

代码如下:

# 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]:
        allnum = []
        for i in range(len(lists)):
            while lists[i] is not None:
                allnum.append(lists[i].val)
                lists[i] = lists[i].next
        allnum.sort()
        head = None
        pnode_pre = None
        for i in range(len(allnum)):
            node = ListNode(allnum[i], None)
            if head is None:
                head = node
                pnode_pre = node
                continue 
            pnode_pre.next = node
            pnode_pre = node
        return head

结果如下:

T23 合并K个升序链表

有点钻空子的嫌疑哈哈哈哈哈哈c

- THE END -

桌桌

8月16日01:10

最后修改:2022年8月16日
0

非特殊说明,本博所有文章均为博主原创。