【Day6】合并两个排序链表与合并k个已排序的链表，java代码实现

前言：
大家好，我是良辰丫🚀🚀🚀，今天与大家一起做两道牛客网的链表题，好久写关于链表题的博客了，这两道题可以帮大家巩固一下链表知识，我把两道题的链接放到下面，大家可以去做一下。💥💟💟💥
题目链接：
合并两个排序链表
合并K个排序链表

🧑个人主页：良辰针不戳
📖所属专栏：EveryDay学java
🍎励志语句：生活也许会让我们遍体鳞伤，但最终这些伤口会成为我们一辈子的财富。
💦期待大家三连，关注，点赞，收藏。
📜作者能力有限，也会出错，希望大家可以指正。
💞愿与君为伴，共探Java汪洋大海。

---

---

1、合并两个排序链表

1.1 题目描述

• 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
• 数据范围： 0 \le n \le 10000≤n≤1000，-1000 \le 节点值 \le 1000−1000≤节点值≤1000
  要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
• 如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

1.2 实例

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

1.3 题目分析

做题不能着急，一定先要读懂题。
这个题目的要求是合并两个有序链表，而且合并后的链表也是有序的。
做题要学的是思想，今天我们主要用到的是虚拟节点。

• 申请一个虚拟的头结点
• cur指向这个虚拟头结点
• while循环进行进行遍历，只要其中一个链表为空结束循环
• 循环里面进行判断，list1和list2谁较小就与cur进行拼接
• 结束循环后，说明至少有一个链表为空，因此，cur拼接不为空的链表；也可能两个都为空，至少拼接一个，因为链表要以null结束。

1.4 代码展示

下面是具体代码，我也会稍微写一点注释帮助大家理解。

public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {//申请虚拟节点ListNode newHead = new ListNode(-1);//cur指向当前的虚拟节点ListNode cur = newHead;//while循环,只要遍历完其中一个链表就结束循环while(list1 != null && list2 != null){if (list1.val < list2.val){//拼接cur.next = list1;cur = cur.next;list1 = list1.next;} else {//拼接cur.next = list2;cur = cur.next;list2 = list2.next; }}//拼接不为空的，两个都遍历完的时候任意拼接一个if(list1 != null){cur.next = list1;}else{cur.next = list2;}return newHead.next;}
}

2、合并K个排序链表

聪明的大家或许已经发现，这道题是刚刚那道题的升级版，牛客网标注着难题的标志，其实也没那么难，找到了规律，掌握了思想，做起来很容易。

2.1 题目描述

• 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
• 数据范围：节点总数 0 \le n \le 50000≤n≤5000，每个节点的val满足 |val| <= 1000∣val∣<=1000
  要求：时间复杂度 O(nlogn)O(nlogn)

2.2 实例

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

2.3 题目分析

做题除了要看懂题，还要注意思想，不要忙于去做题。
先去分析，想明白用什么方法去做。
首先大家肯定会想到粗鲁的办法，从前往后，依次遍历比较，然后进行拼接，这样不仅时间复杂度高，而且比较麻烦，搞的头晕目眩，也不一定能得出正确的答案。那么我们需要想到另一种方法，分治思想，这种思想我们在快排和归并排序中见过，既然接触过，我们肯定有点基础，我们来回忆一下所谓的分治思想。

分治就是分而治之，可以这样理解，解决一个大问题的时候，首先把大问题化解成若干个小问题（小问题与大问题的性质保持一致），逐个解决完小问题，然后合并，最终就解决了所谓的大问题。

总结分治思想：

• 大问题化解为若干个子问题。
• 计算各个子问题。
• 合并所有子问题的解。

看到这里，大家应该对分治思想有了一定的认识，那么接下来我们分析一下这道题。

• 大问题化解成小问题，需要写一个小问题的递归方法，因此我们构造了func(ArrayList lists,int left ,int right)方法。
• 分治思想需要注意边界，这里的左边界和右边界是以链表为单位的，而不是节点。
• 我们还需要一个合并两个有序链表的方法，在上面那道题就是，我们可以直接复制过来。

2.4 代码展示与分析

下面是合并k个有序链表的代码，我会通过注释带大家简单分析一下。

public class Solution {public ListNode mergeKLists(ArrayList<ListNode> lists) {//需要返回一个节点//传参func，参数为集合lists，左边界0和右边界lists.size()-1return func(lists,0,lists.size()-1);}//下面是一个递归方法//也就是大问题化解为小问题的过程private ListNode func(ArrayList<ListNode> lists,int left ,int right){//左边界大于右边界的时候化解结束if(left > right){return null;//左边界等于右边界的时候，返回该节点//因为这里左右节点的下标相同//所以写lists.get(left)或者lists.get(right)都行} else if(left == right){return lists.get(left);//left < right的时候，就要再次进行划分//因为咱们只有合并两个链表的方法} else{int mid = (left + right)  / 2;return merge(func(lists,left,mid),func(lists,mid+1,right));}}//下面的方法就是第一道题的答案，就不做详细说明了private ListNode merge(ListNode list1,ListNode list2){ListNode newHead = new ListNode(-1);ListNode cur = newHead;while(list1 != null && list2 != null){if(list1.val < list2.val){cur.next = list1;cur = cur.next;list1 = list1.next;} else {cur.next = list2;cur = cur.next;list2 = list2.next;}}if(list1 == null){cur.next = list2;} else {cur.next = list1;}return newHead.next;}
}

后序：
我相信大家通过这两道题学到了很多，第一道题比较简单，但大家不要眼高手低，还是多加练习，熟能生巧，第二道题需要掌握分治思想，可能大家一看到递归就会头疼，代码不多，但是却不容易理解，这个东西需要多加练习，琢磨，画图，需要自己不断去品味，去感受，不要畏惧，做的多了，你会感到所谓的递归其实没有那么难。哈哈，今天的内容到这里也就结束了，希望小小的我能够帮助到大家。💞💞💞