美文网首页
【LeetCode】23.合并K个排序链表

【LeetCode】23.合并K个排序链表

作者: 握不住手中沙 | 来源:发表于2020-04-19 20:29 被阅读0次

    题目描述

    23.合并K个排序链表

    合并k个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

    示例:
    输入:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    输出: 1->1->2->3->4->4->5->6
    

    题目解析

    方法一:暴力法

    解题思路

    合并K个排序链表,首先我们直接采用暴力法去解决,将链表所有节点的val值放入一个List中,然后将这个List进行排序,根据排序后的List重新构建新链表。

    代码示例

    Java:

    /**
     * Definition for singly-linked list.
     */
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { 
            val = x;
        }
    }
    
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) return null;
    
            // 1. 将链表节点放入一个List中
            List<Integer> arr = new ArrayList<Integer>();
            for (int i = 0; i < lists.length; i++) {
                ListNode cur = lists[i];
                while(cur != null) {
                    arr.add(cur.val);
                    cur = cur.next;
                }
            }
    
            // 2. 排序
            Collections.sort(arr);
            
            // 3. 重新构建链表
            ListNode res = new ListNode(0);
            ListNode cur = res;
            for(int i = 0; i < arr.size(); i++) {
                ListNode node = new ListNode(arr.get(i));
                cur.next = node;
                cur = cur.next;
            }
            return res.next;
        }
    }
    

    复杂度分析

    时间复杂度:O(N * log(N)), N代表所有链表节点数量。

    • 遍历所有值需要花费O(N)时间
    • 稳定的排序算法花费N * log(N)时间
    • 重新构建链表需要花N * log(N)时间

    空间复杂度:O(N)

    方法二:堆排序法

    解题思路

    采用堆的方式来进行链表节点的排序,创建一个大小为K的小根堆,首先将K个链表的头指针插入到堆中,然后取出堆顶元素,同时将堆顶元素的下一个节点插入到最小堆中,然后循环该操作直至链表节点全部遍历完成。

    代码示例

    Java:

    /**
     * Definition for singly-linked list.
     */
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { 
            val = x;
        }
    }
    
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) return null;
    
            // 1. 初始化小根堆
            PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>() {
                    public int compare(ListNode o1, ListNode o2) {
                        return (o1.val - o2.val);
                    }
                });
            for(int i = 0; i < lists.length; i++) {
                if (lists[i] != null) queue.add(lists[i]);
            }
    
            // 2. 取出堆顶元素,并将堆顶元素的下一节点插入小根堆
            ListNode res = new ListNode(0);
            ListNode cur = res;
            while(!queue.isEmpty()) {
                ListNode top = queue.poll();
                if (top.next != null) {
                    queue.add(top.next);
                }
                cur.next = top;
                cur = cur.next;
            }
            return res.next;
        }
    }
    

    复杂度分析

    时间复杂度:O(N * log(K)),N代表所有链表节点数量,K代表链表的个数。

    空间复杂度:O(K)

    方法三:分治法

    解题思路

    我们将K个链表对半划分,先合并前K/2个链表,再合并后K/2个链表,然后将前K/2个链表合并成的链表再与后K/2个链表合并的链表进行合并,得到最终结果。

    在处理前K/2个和后K/2个链表时,就跟上述方法思路一致,通过递归的方式不停的将链表进行划分,直到链表无法继续划分为止,将链表返回给递归的上一层进行两两合并。

    分治思路:划分子问题 --> 合并子问题结果【递归实现】

    代码示例

    Java:

    /**
     * Definition for singly-linked list.
     */
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { 
            val = x;
        }
    }
    
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) return null;
            return divide(lists, 0, lists.length-1);
        }
    
        public ListNode divide(ListNode[] lists, int lo, int hi) {
            if (lo == hi) return lists[lo];
            int mid = lo + (hi - lo) / 2;
            ListNode left = divide(lists, lo, mid);
            ListNode right = divide(lists, mid + 1, hi);
            return merge(left, right);
        }
    
        public ListNode merge(ListNode l1, ListNode l2) {
            if(l1 == null || l2 == null) {
                return (l1 == null) ? l2 : l1;
            }
            if(l1.val <= l2.val) {
                l1.next = merge(l1.next,l2);
                return l1;
            } else {
                l2.next = merge(l1, l2.next);
                return l2;
            }
        }
    }
    

    复杂度分析

    时间复杂度:O(N * log(K)),N代表所有链表节点数量,K代表链表的个数。

    空间复杂度:O(K)

    相关文章

      网友评论

          本文标题:【LeetCode】23.合并K个排序链表

          本文链接:https://www.haomeiwen.com/subject/crlibhtx.html