首页 > 试题广场 >

合并k个已排序的链表

[编程题]合并k个已排序的链表

热度指数：183582 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数 $0 \le n \le 5000$ ，每个节点的val满足 $|val| <= 1000$

要求：时间复杂度 $O(nlogn)$

示例1

输入

[{1,2,3},{4,5,6,7}]

输出

{1,2,3,4,5,6,7}

示例2

输入

[{1,2},{1,4,5},{6}]

输出

{1,1,2,4,5,6}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

Python3

水彩笔watercol

class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        mark = 1
        head = ListNode(0)
        p = head
        while mark:
            min_v = ListNode(1000)
            mark = 0
            index = 0
            for i in range(0,len(lists)):
                q = lists[i]
                if q != None:
                    mark = 1
                    if min_v.val > q.val:
                        min_v = q
                        index = i
            if mark == 1:
                lists[index] = lists[index].next
                p.next = min_v
                p = p.next
        p.next = None
        head = head.next
        return head

发表于 2024-05-06 15:06:41 回复(0)

Python3

在线蹲牛友的伊登很胖墩墩

用堆不要把全部数据一次性***去，

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#

class ListNodeAddLt:
    def __init__(self, node):
        self.node = node
    def __lt__(self,other):
        return self.node.val < other.node.val

class Solution:
    # 优先队列
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        if lists is None&nbs***bsp;len(lists) == 0:
            return None

        import heapq
        n = len(lists)
        queue = []
        for i in range(n):
            if lists[i]:
                heapq.heappush(queue,ListNodeAddLt(lists[i]))


        if len(queue) == 0:
            return None
        ans = queue[0].node

        prev = ListNode(0)
        while queue:
           node = heapq.heappop(queue).node
           prev.next = node
           prev = node
           if node.next:
                heapq.heappush(queue,ListNodeAddLt(node.next))
        return ans

def __lt__(self,other):

return self.node.val < other.node.val

发表于 2024-04-24 14:18:48 回复(0)

Python3

wit_1905120314

class Solution:

def mergeKLists(self , lists: List[ListNode]) -> ListNode:

# write code here

def getList(list: ListNode):

vals = []

while list:

vals.append(list.val)

list = list.next

return vals

ListVals = []

for list in lists:

ListVals.extend(getList(list))

ListVals.sort()

head = min = ListNode(0)

for val in ListVals:

node = ListNode(val)

min.next = node

min = node

return head.next

编辑于 2023-12-29 15:26:15 回复(0)

Python3

琬圭sakura

使用归并排序的递归算法也可实现该功能，但是有组用例会超时，建议使用堆完成。归并排序算法如下：

from copy import deepcopy
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
class linkList:
    def __init__(self) :
        self.head=ListNode(None)
        pass
class Solution:
    def merge(self,a,b):
        # print(a.val,b.val)
        try:
            a=a[0]
        except:
            pass
        try:
            b=b[0]
        except:
            pass
        # b=b[0]
        c=linkList()
        p=c.head
        while a and b:
            if a.val<b.val:
                temp=deepcopy(a)
                temp.next=p.next
                p.next=temp
                a=a.next
                p=p.next
            else:
                temp=deepcopy(b)
                temp.next=p.next
                p.next=temp
                b=b.next
                p=p.next
        if a:
            p.next=a
        else:
            p.next=b      
        return c.head.next

    def merge_sort(self,lists):
        if len(lists)==1:
            return lists[0]
        if len(lists)==0:
            return None
        mid=len(lists)//2
        left=self.merge_sort(lists[:mid])
        right=self.merge_sort(lists[mid:])
        return self.merge(left,right)

    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # write code here
        # print(self.merge_sort(lists))
        return self.merge_sort(lists)

发表于 2023-09-23 17:09:04 回复(1)

Python3

pzq

class Solution:
    def is_all_None(self, lists):
        for node in lists:
            if node is not None:
                return False
        return True

    def min_not_None(self, lists):
        p_min = lists[0]
        ind_min = 0
        for ind,node in enumerate(lists[1:]):
            if p_min is None and node is not None:
                p_min = node
                ind_min = ind + 1
            if p_min is not None and node is not None:
                if node.val < p_min.val:
                    p_min = node
                    ind_min = ind + 1
        lists[ind_min] = lists[ind_min].next
        return p_min, lists

    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # write code here
        pHead = ListNode(-1)
        p = pHead
        while not self.is_all_None(lists):
            # 选出非None的最小值并更新lists
            p_min_node, lists = self.min_not_None(lists)
            p.next = p_min_node
            p = p.next
        return pHead.next

发表于 2023-09-05 01:06:24 回复(0)

Python3

牛客661913874号

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# @param lists ListNode类一维数组

# @return ListNode类

class Solution:

def mergeKLists(self , lists: List[ListNode]) -> ListNode:

my_list = []

for linklist in lists:

cur = linklist

# print(cur)

while cur:

my_list.append(cur.val)

# print(cur.val)

cur = cur.next

my_list.sort

# print(my_list)

node = ListNode(0)

tem = node

for i in my_list:

node.next = ListNode(i)

node = node.next

return tem.next

发表于 2023-07-17 15:34:56 回复(0)

Python3

啊没事的都可以理解

HEAPQ python实现

import heapq
class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # write code here
        heap = []
        count = 0 
        for node in lists:
            if node:
                heap.append((node.val,count,node))
                count+=1
        heapq.heapify(heap)
        retval = ListNode(-1)
        cur = retval
        while heap:
            cur.next = heapq.heappop(heap)[2]
            cur = cur.next
            if cur.next:
                heapq.heappush(heap,(cur.next.val,count,cur.next))
                count+=1
        return retval.next

发表于 2023-06-10 22:55:12 回复(0)

Python3

神奇的神仙在深空

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
import copy

class Solution:
    def get_head(self, head):
        return copy.deepcopy(head)

    def delete_head(self, head):
        return head.next

    def insert_node(self, head, node):
        node.next = head.next
        head.next = node
        return head

    def find_insert_position(self, head, current_node):
        while(head != None and head.next != None and head.next.val < current_node.val):
            head = head.next
        return head

    def merge(self, base_list, compared_list):
        virtual_head = ListNode(None)
        virtual_head.next = base_list

        insert_position = virtual_head
        while(compared_list):
            current_node = self.get_head(compared_list)
            insert_position = self.find_insert_position(insert_position, current_node)
            self.insert_node(insert_position, current_node)
            compared_list = self.delete_head(compared_list)

        return virtual_head.next

    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # write code here
        if len(lists) < 2:
            return lists[0] if lists else None
        base_list = lists[0]
        for compared_list in lists[1:]:
            base_list = self.merge(base_list, compared_list)
        return base_list

发表于 2023-03-10 17:36:21 回复(0)

Python3

snowy_shanghai

    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # write code here
        n = len(lists)
        nh1 = ListNode(0)
        nh2 = nh1

        flag = False
        for i in lists:
            if i:
                flag = True
                break

        while flag:
            for i in range(len(lists)):
                if lists[i]:
                    flag = True
                    break
            if not flag:
                break
            minnum = 1001
            index = -1
            for i in range(len(lists)):
                if lists[i]:
                    if lists[i].val < minnum:
                        minnum = lists[i].val
                        index = i
            if index < 0:
                break
            nh2.next = lists[index]
            lists[index] = lists[index].next            
            nh2 = nh2.next
        return nh1.next

发表于 2023-03-02 00:25:35 回复(0)

Python3

西南第一深情

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# @param lists ListNode类一维数组 
# @return ListNode类
#归并排序思路
#1.链表列表两两分组分别按大小升序排序（构建对两个升序链表排序的方法）
#2.每组排序完成的链表添加到新链表列表中
#3.循环1-2，直至新链表列表长度为1，此时列表首项的链表即为排序后链表
class Solution:
    #两链表排序方法
    def twoLN(self,pHead1,pHead2):
        shaobing = ListNode(-1)
        p1 = pHead1
        p2 = pHead2
        p = shaobing
        while p1 and p2:
            if p1.val <= p2.val:
                temp = p1.next
                p1.next = None
                p.next = p1
                p1 = temp
                p = p.next
            else:
                temp = p2.next
                p2.next = None
                p.next = p2
                p2 = temp
                p = p.next
        if p1:
            p.next = p1
            p = p.next
        if p2:
            p.next = p2
            p = p.next
        return shaobing.next

    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # write code here
        #列表为空，返回空链表头
        if len(lists) == 0:
            return None
        while len(lists) > 1:
            new_lists = []
            for i in range(0,len(lists),2):
                #列表中每相邻两个链表做排序后将结果添加至新列表
                if i < len(lists) - 1:
                    new_lists.append(self.twoLN(lists[i],lists[i+1]))
                #如果列表长度为单数，将最后一项直接添加至新列表中
                else:
                    new_lists.append(lists[i])
            lists = new_lists
        return lists[0]

发表于 2022-12-10 14:35:22 回复(0)

Python3

牛客879332223号

基本思路：二分，然后合并左边跟右边

class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
# 特殊情况特殊处理
        if len(lists)==0:
            return None
        if len(lists)==1:
            return lists[0]
        mid=len(lists)//2
        left =self.mergeKLists(lists[:mid])
        right=self.mergeKLists(lists[mid:])
## 下面就是合并两个有序链表的代码了。
        dummy=ListNode(-1)
        curr=dummy
        while left and right:
            if left.val < right.val:
                curr.next=left
                left=left.next
            else:
                curr.next=right
                right=right.next
            curr=curr.next
        curr.next=left&nbs***bsp;right
        return dummy.next

发表于 2022-09-21 09:02:46 回复(0)

Python3

Keosu

基本思路，增加一个虚拟头节点，每次从k个链表中挑选出最小的加入到尾部，再把该链表往后移动，如果是每次k个直接比较，则复杂为O(nk)，考虑到每次比较只更新一个元素，因此可以得到O(nlogk)的方法，这里使用堆。

import heapq
class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        vhead = ListNode(-1)
        p = vhead 
        
        heads = [i for i in lists]
        heap = [(n.val,idx) for idx, n in enumerate(lists) if n is not None]
        heapq.heapify(heap)
        
        while heap:
            idx = heapq.heappop(heap)[1] #
            tmp = heads[idx]
            p.next = tmp
            heads[idx] = heads[idx].next
            p = p.next
            if heads[idx]: heapq.heappush(heap,(heads[idx].val, idx)) 
                
        return vhead.next

发表于 2022-07-31 17:22:20 回复(0)