2022-9-7合并k个已排序的链表---困难

上链接：2022-9-7

合并k个已排序的链表_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6人生第一次写出来一个 “较难” 类型的题！！！谨此纪念！

目录

题目描述：

解决思路：

---

题目描述：

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

范围：

节点总数>=0  、链表个数 >= 1 、 链表长度 >= 1

示例1：

输入：[{1,2,3},{4,5,6,7}]

返回值：{1,2,3,4,5,6,7}

示例2：

输入：[{1,2},{1,4,5},{6}]

返回值：{1,1,2,4,5,6}

初始代码：

import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList lists) {
        
    }
}

解决思路：

1、先写一个功能函数merge，能够将两个有序链表合并成一个有序链表

2、按照顺序 一个个合并每一个链表！

失误点：时间复杂度过高！代码运算超时！

如何解决：  利用归并的思想！

• step 1：从链表数组的首和尾开始，每次划分从中间开始划分，划分成两半，得到左边n/2个链表和右边n/2个链表。
• step 2：继续不断递归划分，直到每部分链表数为1.
• step 3：将划分好的相邻两部分链表，按照两个链表合并的方式合并，合并好的两部分继续往上合并，直到最终合并成一个链表。

import java.util.*;
 
public class Solution {
    private ListNode merge(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) {
            return null;
        } else if (list1 != null && list2 == null) {
            return list1;
        } else if (list1 == null) {
            return list2;
        }
        ListNode ret = new ListNode(0);
        ListNode cur = ret;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                ListNode node = new ListNode(list1.val);
                cur.next = node;
                list1 = list1.next;
            } else {
                ListNode node = new ListNode(list2.val);
                cur.next = node;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if (list1 == null) {
            cur.next = list2;
        } else {
            cur.next = list1;
        }
        return ret.next;
    }
//！！时间超时的原本代码
    //    public ListNode mergeKLists(ArrayList lists) {
//        if (lists.isEmpty()){
//            return null;
//        }
//        ListNode[] arr = new ListNode[lists.size()];
//        lists.toArray(arr);
//        int index = arr.length;
//        ListNode ret = merge(arr[index-1],arr[index-2]);
//        index-=3;
//        while(index>=0){
//            ret=merge(ret,arr[index]);
//            index--;
//        }
//        return ret;
//    }
 
//下面是改进后的代码
    public ListNode mergeKLists(ArrayList lists) {
        ListNode[] arr = new ListNode[lists.size()];
        lists.toArray(arr);
        return merge1(arr, 0, arr.length - 1);
    }
 
    private ListNode merge1(ListNode[] arr, int left, int right) {
        if (left>right){
            return null;
        }else if (left==right){
            return arr[left];
        }
        int mid = (left+right)/2;
//重点要读懂这一句！！
        return merge(merge1(arr,left,mid),merge1(arr,mid+1,right));
    }
}