目录

AaronJny

诗酒繁华,书剑天涯。

leetcode题解第23题 Merge k Sorted Lists(合并K个排序链表)

题目大意如下:

给定 k 个有序链表,请将这 k 个列表合并成一个有序链表,然后返回这个有序列表的头结点。

在 python 中,链表被这样实现:

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

样例输入:

[
1->4->5,
1->3->4,
2->6
]

样例输出:

1->1->2->3->4->4->5->6

题目链接:https://leetcode.com/problems/merge-k-sorted-lists

解题思路:

这道题考察的是链表的操作和归并排序,只不过这里做的是多个列表的归并。

输入是一个链表头结点组成的列表,我们需要创建一个指向这些链表头结点的指针构成的列表,和一个结果链表。

比较所有指针对应的值的大小,获取最小的节点的值,创建新节点,加入到结果链表中。然后将指向最小节点的指针后移一位。当一个指针走到头时,这个指针将被从指针列表中移除。

重复上一步操作,直到指针列表为空,返回结果链表即可。

样例代码:

class Solution:

    def mergeKLists(self, lists):
        # 结果链表头结点
        ln = None
        # 指向结果链表的指针
        pn = None
        # 指向给定链表列表的指针列表,其中空链表将不会加入列表中
        ps = [node for node in lists if node]
        # 当指针列表不为空时
        while len(ps) and all(ps):
            # 指针列表中,指向节点的值最小的指针在列表中的下标,默认为0
            min_px = 0
            # 指针指向节点的最小值,默认为第一个指针指向结果的值
            min_num = ps[0].val
            # 检查所有指针指向节点,找出节点值最小的指针
            for i in range(1, len(ps)):
                # 当碰到值更小的节点时,更新最小节点指针在列表中的下标和最小值
                if ps[i].val < min_num:
                    min_px = i
                    min_num = ps[i].val
            # 这时,我们已经获取到了本次最小的值,创建一个新节点
            tmp_node = ListNode(min_num)
            # 将它加入到结果链表中
            # 当结果链表头结点为空时
            if ln is None:
                # 使用这个节点作为头结点
                ln = tmp_node
                # 结果链表的指针指向这个节点
                pn = tmp_node
            # 当不为空时
            else:
                # 结果链表的指针的next指向这个节点
                pn.next = tmp_node
                # 结果链表指针后移一位
                pn = pn.next
            # 值最小的节点对应的指针后移一位
            ps[min_px] = ps[min_px].next
            # 剔除掉走到头的指针,重复上述操作
            ps = [node for node in ps if node]
        # 返回结果链表
        return ln

转载请注明出处:https://blog.csdn.net/aaronjny/article/details/88792346


标题:leetcode题解第23题 Merge k Sorted Lists(合并K个排序链表)
作者:AaronJny
地址:https://aaronjny.com/articles/2019/11/06/1573017881785.html