每日刷题之合并k个升序数组（牛客）

59 阅读 0 评论 39 点赞

我是靠谱客的博主开心画板，最近开发中收集的这篇文章主要介绍每日刷题之合并k个升序数组（牛客），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

- 思路
- 代码
- 复杂度
- ????结语

✅作者简介：我是18shou，一名即将秋招的java实习生

????系列专栏：牛客面经专栏

????推荐一款八股、面经、模拟面试、刷题神器???? 超级无敌牛逼之牛客
在这里插入图片描述
此题需要先掌握合并俩个有序链表

思路

将 k 个链表配对并将同一对中的链表合并；
第一轮合并以后， k 个链表被合并成了 k/2 个链表，平均长度为 2n/k，然后是 k/4 个链表， k/8个链表等等；
重复这一过程，直到我们得到了最终的有序链表。

代码

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    ListNode ans;
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        return merge(lists, 0, lists.size() - 1);
    }
     public ListNode merge(ArrayList<ListNode> lists, int l, int r) {
        if (l == r) {
            return lists.get(l);
        }
        if (l > r) {
            return null;
        }
        int mid = l + (r - l) / 2;
        ListNode left = merge(lists, l, mid);
        ListNode right = merge(lists, mid + 1, r);
        return mergeTwoLists(left,right);
    }
    public ListNode mergeTwoLists(ListNode list1,ListNode list2) {
        ListNode l1= list1;
        ListNode l2 = list2;
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while(l1 != null && l2 !=null) {
            if(l1.val > l2.val) {
                cur.next = l2;
                l2 = l2.next;
            }else{
                cur.next = l1;
                l1 = l1.next;
            }
            cur = cur.next;
        }
        if(l1 != null) {
            cur.next = l1;
        }
        if(l2 != null) {
            cur.next = l2;
        }
        return head.next;
    }
}

在这里插入图片描述