`

Leetcode - Merge k Sorted Lists

 
阅读更多
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

[分析] 有了Merge 2 sorted lists的铺垫做这题就容易了,自己写了递归版的method1, 翻看历史记录,有迭代版的和heap sort版本,觉得method1 & 2写得更顺手些。感觉迭代方式挺巧妙的,哈哈

public class Solution {
    // Method 1: 递归
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;
        return divide(lists, 0, lists.length - 1);
    }
    private ListNode divide(ListNode[] lists, int beg, int end) {
        if (beg != end) {
            int mid = beg + (end - beg) / 2;
            return merge2Lists(divide(lists, beg, mid), divide(lists, mid + 1, end));
        } else {
            return lists[beg];
        }
    }
    // Method 2: 迭代
    public ListNode mergeKLists2(ArrayList<ListNode> lists) {
        int last = lists.size() - 1;
        if(last < 0)
            return null;
        
        while(last > 0){
            int curr = 0;
            while(curr < last)
                lists.set(curr, merge2Lists(lists.get(curr++), lists.get(last--)));
        }
        return lists.get(0);
    }
    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode head = new ListNode(0);
        ListNode m = head;
        ListNode p = l1, q = l2;
        while (p != null && q != null) {
            if (p.val < q.val) {
                m.next = p;
                p = p.next;
            } else {
                m.next = q;
                q = q.next;
            }
            m = m.next;
        }
        if (p != null)
            m.next = p;
        if (q != null)
            m.next = q;
        return head.next;
    }
    // Method 3: heap sort(O(nlogk)), n nodes, k lists
     public ListNode mergeKLists(ArrayList<ListNode> lists) {
        
        if(lists == null || lists.size() == 0)
            return null;
        
        Comparator<ListNode> comparator = new Comparator<ListNode>(){
            public int compare(ListNode l1, ListNode l2){
                if(l1.val < l2.val) 
                    return -1;
                else if(l1.val > l2.val) 
                    return 1;
                else 
                    return 0;
            }
        };
        
        //initial 
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), comparator);
        for(ListNode node:lists){
            if(node != null)
                heap.offer(node);
        }
        
        ListNode head = null, curr = head;
        while(!heap.isEmpty()){
            if(head == null){
                head = heap.poll();//delete min from heap
                curr = head;
            }else{
                curr.next = heap.poll();
                curr = curr.next;
            }
            if(curr.next != null)
                heap.offer(curr.next);
        }
        
        return head;    
    }
}
分享到:
评论

相关推荐

    c语言-leetcode 0023-merge-k-sorted-lists.zip

    c c语言_leetcode 0023_merge_k_sorted_lists.zip

    js-leetcode题解之23-merge-k-sorted-lists.js

    最终,题解文件“js-leetcode题解之23-merge-k-sorted-lists.js”将为leetcode用户和JavaScript开发者提供一个清晰的解题思路和一个可靠的代码实现,帮助他们更好地理解和掌握如何合并多个排序链表,以及如何在实际...

    c语言-leetcode 0021-merge-two-sorted-lists.zip

    c c语言_leetcode 0021_merge_two_sorted_lists.zip

    C语言-leetcode题解之21-merge-two-sorted-lists.c

    “C语言-leetcode题解之21-merge-two-sorted-lists.c”不仅为初学者提供了一道链表操作的经典题目,更是引导其深入理解链表结构和指针操作的一个有效途径。通过不断的练习和思考,可以快速提升编程能力和解题技巧,...

    js-leetcode题解之21-merge-two-sorted-lists.js

    今日我们要分析的题目是LeetCode上的一道经典题目——合并两个有序链表(Merge Two Sorted Lists)。该题目要求编写一个函数,将两个已排序的链表合并为一个新的有序链表,并且返回新的链表头节点。这里提到的链表是...

    LeetCode Merge 2 Sorted Lists解决方案

    LeetCode Merge 2 Sorted Lists解决方案详解 Merge 2 Sorted Lists是LeetCode上的一个经典算法题目,旨在考察程序员对链表的操作和排序算法的掌握程度。下面对该题目的解决方案进行详细的分析和解释。 问题描述 ...

    _leetcode-python.pdf

    - Merge k Sorted Lists: 合并k个排序链表。 - Swap Nodes in Pairs / Reverse Nodes in k-Group: 这两个问题涉及到在链表中按特定规则交换节点或反转节点组。 - Remove Duplicates from Sorted Array / Remove ...

    leetcode-链表笔记

    Merge Two Sorted Lists**:合并两个已排序的链表,保持排序顺序。 - **142. Linked List Cycle II**:找到链表环的长度,并给出进入环的第一个节点。 4. **解决链表问题的策略** - **迭代法**:使用循环遍历...

    多线程leetcode-leetcode-java:leetcode上的题解,基于java语言

    多线程 leetcode 前言 每天刷点leetcode,基于java语言实现。 leetcode上难度分三档:easy,medium,hard. 如下: easy medium ...Merge k Sorted Lists Reverse Nodes in k-Group Trapping Rain Water

    leetcode答案-LeetCode-Trip:LeetCode刷题代码,大佬勿入

    Merge Two Sorted Lists] [53. Maximum Subarray] [70. Climbing Stairs] [101. Symmetric Tree] [104. Maximum Depth of Binary Tree] [121. Best Time to Buy and Sell Stock] [167. Two Sum II - Input array is ...

    gasstationleetcode-leetcode-rust:莱特代码休息

    加油站 leetcode 力码锈 问题 # 标题 命令 1 cargo run --bin 1-two-sum 2 cargo run --bin 2-add-two-numbers 3 cargo run ...21-merge-two-sorted-lists 27 cargo run --bin 27-remove-element 28

    leetcode中文版-LeetCode:力码

    leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部注释,后续会持续更新。 有不懂的可以联系ji648513181,同时也欢迎志同道合O的朋友一起合作更新。 已更新剑指Offer答案...

    MergeTwoSortedLinkedList.java

    【Leetcode】Merge Two Sorted Lists

    程序员面试宝典LeetCode刷题手册

    第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters ...23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli

    lrucacheleetcode-leetcode-journal:记录所有LeetCode挑战的存储库

    lru缓存leetcode 力扣日记 欢迎来到我的 LeetCode 期刊库。 我的每个问题都将包括一个初始计划...k Sorted Lists (Hard) 31. Next Permutation (Medium) 34. Find First and Last Position of Element in Sorted Arr

    Leetcode-best-DSA-问题:必须执行这些leetcode编码问题以提高您的问题解决能力

    LeetCode中的这类问题涵盖了排序、查找、反转等操作,如“两数之和”(Two Sum)、“旋转数组”(Rotate Array)和“合并两个有序链表”(Merge Two Sorted Lists)。 2. **栈和队列**:这两种线性结构在处理逆序...

    leetcode-answer-and-analysis(part).zip_图形图像处理_Java_

    10. **Merge Two Sorted Lists** (合并两个排序链表): 这是一个经典的链表操作问题,通过比较两个链表的当前节点值,选择较小的一个插入新的链表中,直到其中一个链表为空。在Java中,可以使用临时节点来构建新的...

    leetcode备忘录系统-Algorithms-DataStructures:算法-数据结构

    leetcode备忘录系统算法-数据结构 两个不错的排序算法及其 Big-O(完成) 归并排序 快速排序 冒泡排序 基本数据结构实现及其 Big-O 复杂性 哈希图 堆 队列 双端队列双端队列 链表 反转链表 合并两个排序列表 回文...

    leetcode中325题python-leetcode:leetcode

    merge-two-sorted-lists 82 删除排序链表中的重复元素 II remove-duplicates-from-sorted-list ii 83 删除排序链表中的重复元素 remove-duplicates-from-sorted-list 86 分隔链表 partition-list 92 反转链表 II ...

Global site tag (gtag.js) - Google Analytics