美文网首页
合并k个有序链表

合并k个有序链表

作者: 最困惑的时候就是能成长的时候 | 来源:发表于2019-05-27 22:26 被阅读0次

23. 合并K个排序链表

1.想法

不能每一个都进行比较那么比较合适是的归并排序
每次都两两合并,和归并排序的流程一样

2.代码

 public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0)return null;
        ListNode result = mergeMyKLists(lists,0,lists.length-1);
        return result;
    }

private ListNode mergeMyKLists(ListNode[] lists, int left, int right) {
         if(left==right)return lists[left];
        //分左右两个ListNode
        ListNode leftNodes = mergeMyKLists(lists, left, (right - left) / 2 + left);
        ListNode rightNodes = mergeMyKLists(lists, (right - left) / 2 + left + 1, right);

       //合并左右两个ListNode
        if(leftNodes == null)return rightNodes;
        if(rightNodes == null)return leftNodes;

        ListNode newNode = null;
        if(leftNodes.val<rightNodes.val){
            newNode = new ListNode(leftNodes.val);
            leftNodes = leftNodes.next;
        }else{
            newNode = new ListNode(rightNodes.val);
            rightNodes = rightNodes.next;
        }
        ListNode newHead = newNode;
        while(leftNodes!=null&&rightNodes!=null){
            if(leftNodes.val<rightNodes.val){
                newHead.next=new ListNode(leftNodes.val);
                leftNodes = leftNodes.next;
            }else{
                newHead.next=new ListNode(rightNodes.val);
                rightNodes = rightNodes.next;
            }
            newHead = newHead.next;
        }
        if(leftNodes!=null){
            newHead.next = leftNodes;
        }
        if(rightNodes!=null){
            newHead.next = rightNodes;
        }
        return newNode;
    }

相关文章

  • 2022-02-23 链表专栏

    链表基础 类别 1、合并两个有序链表2、合并 k 个有序链表3、寻找单链表的倒数第 k 个节点4、寻找单链表的中点...

  • 2018-12-26

    问题列表 合并两个有序链表 合并K个排序链表 合并区间 插入区间 问题与反馈 总结与收获 多个有序链表的合并,类似...

  • LeetCode-23-合并K个有序链表

    LeetCode-23-合并K个有序链表 题目 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂...

  • LeetCode 专题 :分治算法

    LeetCode 第 23 题:归并多个有序链表 传送门:23. 合并K个排序链表。 合并 k 个排序链表,返回合...

  • 链表操作

    合并2个有序链表 合并k个有序链表 这俩题挺好的,既考察了合并,又考察了递归与分治。 删除倒数第k个节点 思路到没...

  • 06-17:刷题总结

    1、合并k个有序链表 https://leetcode-cn.com/problems/merge-k-sorte...

  • 合并k个有序链表

    题目(来自力扣题库) 思路1 (比较笨的解法) 将所有节点添加到一个数组中 将数组的节点从小到大排序 从数组中从小...

  • 合并K个有序链表

    题目:合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 思路: 把每个链表得头放进小...

  • 合并k个有序链表

    23. 合并K个排序链表 1.想法 不能每一个都进行比较那么比较合适是的归并排序每次都两两合并,和归并排序的流程一...

  • 合并 k 个有序链表

    问题描述 leetcode 23, Merge k Sorted Lists解题思路合并2个有序链表的进阶版,很...

网友评论

      本文标题:合并k个有序链表

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