LeetCode：23. Merge k Sorted Lists（K个链表进行排序）

客官°小女子只卖身不卖艺 2022-04-08 12:14 117阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java方法1：(利用类似的二路归并排序，递归的方式)

python实现方式1：

源码github地址：https://github.com/zhangyu345293721/leetcode

--------------------

### 题目描述： ###

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

--------------------

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

--------------------

### java方法1：(利用类似的二路归并排序，递归的方式) ###

/**
         * @param lists 要合并的链表
         * @return 链表
         */
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length < 1) {
                return null;
            }
            return helper(lists, 0, lists.length - 1);
        }
    
        /**
         * 终止条件是l和r相等
         *
         * @param lists 链表
         * @param l     左边
         * @param r     右边
         * @return 合并后链表
         */
        private ListNode helper(ListNode[] lists, int l, int r) {
            if (l == r) {
                return lists[l];
            }
            int mid = (l + r) / 2;
            return merge(helper(lists, l, mid), helper(lists, mid + 1, r));
        }
    
        /**
         * 通过指针合并两个链表
         *
         * @param l1 链表1
         * @param l2 链表2
         * @return 合并两个链表
         */
        private ListNode merge(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(-1);
            ListNode tail = dummy;
            while (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    tail.next = l1;
                    l1 = l1.next;
                } else {
                    tail.next = l2;
                    l2 = l2.next;
                }
                tail = tail.next;
            }
            if (l1 != null) {
                tail.next = l1;
            }
            if (l2 != null) {
                tail.next = l2;
            }
            return dummy.next;
        }

时间复杂度：O(logn.n)

空间复杂度：O(n)

--------------------

### python实现方式1： ###

from typing import List
    
    from list.linked_list_cycle2_142 import ListNode
    
    
    
    def helper(lists: List[ListNode], l: int, r: int) -> ListNode:
        '''
            递归帮助类
        Args:
            lists: 链表
            l: 坐标
            r: 右边
        Returns:
           合并后链表
        '''
        if l == r:
            return lists[l]
        mid = (l + r) / 2
        return merge(helper(lists, l, mid), helper(lists, mid + 1, r))
    
    
    def merge_k_list(lists: List[ListNode]) -> ListNode:
        '''
            熟悉合并链表
        Args:
            lists:链表
        Returns:
            合并后的list
        '''
        if not lists:
            return None
        return helper(lists, 0, len(lists) - 1)
    
    def merge(l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(-1)
        tail = dummy
        while l1 != None and l2 != None:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        if l1 != None:
            tail.next = l1
        if l2 != None:
            tail.next = l2
        return dummy.next

时间复杂度：O(logn.n)

空间复杂度：O(n)

--------------------

### java方法2： ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists == null || lists.length < 1) {
                return null;
            }
            PriorityQueue<ListNode> queue = new PriorityQueue(
                new Comparator<ListNode>() {
                @Override
                public int compare(ListNode q1, ListNode q2) {
                return q1.val - q2.val;
                }
            }
            );
            int k = lists.length;
            for(int i = 0;i < k; i++) {
                if(lists[i] != null ){
                    queue.offer(lists[i]);
                }
            }
            ListNode dummy = new ListNode(-1);
            ListNode tail = dummy;
            while(!queue.isEmpty()){
                ListNode cur = queue.poll();
                tail.next = cur;
                tail = tail.next;
                if(cur.next != null) {
                    queue.offer(cur.next);
                }
            }
            return dummy.next;
        }
    }

时间复杂度：O(logn.n)

空间复杂度：O(n)

--------------------

### python方法2： ###

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    import heapq
    
    class Solution:
        def mergeKLists(self, lists: List[ListNode]) -> ListNode:
            dummy = ListNode(0)
            p = dummy
            head = []
            k = len(lists)
            for i in range(k):
                if lists[i] :
                    heapq.heappush(head, (lists[i].val, i))
                    lists[i] = lists[i].next
            while head:
                val, idx = heapq.heappop(head)
                p.next = ListNode(val)
                p = p.next
                if lists[idx]:
                    heapq.heappush(head, (lists[idx].val, idx))
                    lists[idx] = lists[idx].next
            return dummy.next

时间复杂度：O(logn.n)

空间复杂度：O(n)

--------------------

### 源码github地址： ###

**[GitHub - zhangyu345293721/leetcode: java/python for leetcode][GitHub - zhangyu345293721_leetcode_ java_python for leetcode]**

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[GitHub - zhangyu345293721_leetcode_ java_python for leetcode]: https://github.com/zhangyu345293721/leetcode