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

缺乏、安全感 2022-02-28 08:38 202阅读 0赞

题目大意如下：

> 给定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][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][https_blog.csdn.net_aaronjny_article_details_88792346]

[https_leetcode.com_problems_merge-k-sorted-lists]: https://leetcode.com/problems/merge-k-sorted-lists
[https_blog.csdn.net_aaronjny_article_details_88792346]: https://blog.csdn.net/aaronjny/article/details/88792346