合并升序链表系列（Java）

我不是女神ヾ 2024-03-30 12:42 42阅读 0赞

LeetCode原题链接:

*  [21. 合并两个有序链表 - 力扣（LeetCode）][21. _ - _LeetCode]
 *  [23. 合并K个升序链表 - 力扣（LeetCode）][23. _K_ - _LeetCode]

**目录**

合并两个有序链表:

题目表述:

解法一：

解法二：

合并K个升序链表

题目描述：

解法一：

解法二：

--------------------

## 合并两个有序链表: ##

### 题目表述: ###

> 将两个升序链表合并为一个新的 **升序** 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
> 
> ![24ec334c8b8200740378119441f98698.jpeg][]
> 
> 样例:
> 
>     输入：l1 = [1,2,4], l2 = [1,3,4]
>     输出：[1,1,2,3,4,4]

#### 解法一： ####

对于这道题，我们可以创建一个新的头节点res，用于保存头节点，我们需要根据情况的不同进行不同的处理：

>  *  l1.val>l2,val，此时我们只将【l1.val】添加到res中，【l1】后移，【cur】后移
>  *  l2.val>l1.val，此时我们只将【l2.val】添加到res中，【l2】后移，【cur】后移
>  *  l1 == null && l2 == null，此时我们需要将两个节点都加进去（此处我们一起加两个是因为那个没被选到的值在下次比较一定会被加进去，所以索性一次把事情做完），但是要注意的是，我们在添加一个节点后，需要立马将【cur】后移，这样才能将节点正确添加到末尾（这里不懂想想尾插法）
>  *  l1 != null && l2 == null，此时我们只对【l1】处理即可，处理完后移cur指针
>  *  l1 != null && l2 == null，此时我们只对【l1】处理即可，处理完后移cur指针

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode res = new ListNode(0);
            ListNode cur = res;
            while(l1 != null || l2 != null){
                if(l1 !=null && l2 != null){
                    //但两个节点相等，一起添加
                    if(l1.val == l2.val){
                        cur.next = new ListNode(l1.val);
                        //在对链表进行添加元素后要立马将cur后移才能正确添加新节点
                        cur = cur.next;
                        cur.next = new ListNode(l2.val);
                        l1 = l1.next;
                        l2 = l2.next;
                    }else{
                        if(l1.val>l2.val){
                            cur.next = new ListNode(l2.val);
                            l2 = l2.next;
                        }else{
                            cur.next = new ListNode(l1.val);
                            l1 = l1.next;
                        }
                    }
                //到这说明li不为null,l2为null
                }else if(l1!=null){
                    cur.next = new ListNode(l1.val);
                    l1 = l1.next;
                //同上
                }else if(l2!=null){
                    cur.next = new ListNode(l2.val);
                    l2 = l2.next;
                }
                //讲主链表（res）的尾指针也就是cur往后面移动方便添加
                cur = cur.next;
            }
            //因为节点都是往res后面添加的，所以返回的是res.next,而不是res
            return res.next;
        }

效率：

![94f5215cd855414ab3aa2f4f64fd116b.png][]

#### 解法二： ####

基于对解法一的了解，我们有了解法二，这次不是对res采用添加节点的方法了，而是将两个链表连接起来。如下图示例（连接方式不唯一）：

![86072d422754454a99b19a1a36140784.png][]

有一定基础的同学应该发现了，我们只需要定好一个节点为头节点，然后逐个连接起来就可以了，所以这里我们需要三个节点指针【pre：表示结果列表的尾指针】、【cur1：表示一条链表的节点指针】、【cur2：表示一条链表的节点指针】，就拿我们这个图例举例说明：![b8b86f55336b46c89aafdfd434f1a8a7.png][]

所以由图可以看出我们的连接工作就是只**移动被选择的那个节点所在的链表即可（cur后移），**当然pre同样也需要后移。

在我们了解如何连接后，该如何确定pre是哪一条链表上的节点呢？cur1和cur2指向是如何进行确定的呢？？我们通过代码来进行说明：

ListNode head = list1.val<=list2.val?list1:list2;
    // cur1指向头,方便确认cur2的指向
    ListNode cur1 = head;
    // 判断节点为1,还是2,如果为1,就让cur2 指向2,如果为2,就指向1,
    ListNode cur2 = head==list1? list2:list1;
    ListNode pre = head;
    cur1 = head.next;

使用一个名为head的节点直接指向首节点最小的那个链表，这时就可以知道【cur2】的节点指向了，使用head==list1? list2:list1来判断，**假如head是list2,那么【cur2】指向list1,否则指向list2**，也很好理解，它的指向肯定是head的下一位，【pre】开始就是head这个也好理解。那么接下里就是我们的处理过程了

while(cur1 != null && cur2 != null){
        if(cur1.val<=cur2.val){
            pre.next = cur1;
            cur1 = cur1.next;
        }else if(cur1.val > cur2.val){
            pre.next = cur2;
            cur2 = cur2.next;
        }
        pre = pre.next;
    }
    pre.next = cur1 != null? cur1 : cur2!= null?cur2:null;

一目了然，就单纯的链表拼接流程，一个拼接两个后移，最后判断哪个链表没有被遍历完，即将其添加到【pre】屁股后面。

> 注意，我们的循环条件是【&&】，不是解法一中的【 || 】

完整代码：

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if(list1 == null || list2 == null){
                return list1 == null?list2:list1;
            }
            ListNode head = list1.val<=list2.val?list1:list2;
            // cur1指向头,方便确认cur2的指向
            ListNode cur1 = head;
            // 判断节点为1,还是2,如果为1,就让cur2 指向2,如果为2,就指向1,
            ListNode cur2 = head==list1? list2:list1;
            ListNode pre = head;
            cur1 = head.next;
            while(cur1 != null && cur2 != null){
                if(cur1.val<=cur2.val){
                    pre.next = cur1;
                    cur1 = cur1.next;
                }else if(cur1.val > cur2.val){
                    pre.next = cur2;
                    cur2 = cur2.next;
                }
                pre = pre.next;
            }
            pre.next = cur1 != null? cur1 : cur2!= null?cur2:null;
            return head;
        }

效率：

![268a7cbf47be4697ae6301551801b5c4.png][]

## 合并K个升序链表 ##

### 题目描述： ###

> 给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
> 
> 输入：lists = \[\[1,4,5\],\[1,3,4\],\[2,6\]\]  
> 输出：\[1,1,2,3,4,4,5,6\]  
> 解释：链表数组如下：  
> \[  
> 1->4->5,  
> 1->3->4,  
> 2->6  
> \]  
> 将它们合并到一个有序链表中得到：  
> 1->1->2->3->4->4->5->6

在了解了上面的合并链表后，我们也可以基于这两个不同的解法，实现多链表的合并

#### 解法一： ####

在【合并两个升序链表】中，我们需要知道谁是最小就能做到添加节点的操作，但是在多链表中，我们该如何之后多链表的首节点谁最小呢？暴力枚举，简单粗暴，对链表数组进行遍历，记录最小值

for(int j = 0; j < n; j++){
        if(lists[j] != null){
            //获取最小值
            min = Math.min(min,lists[j].val);
         }
    }

在我们获取到最小值后，再次对链表数组进行遍历，只要这些链表的首元素等于最小值，我们就将其节点添加到【res：答案链表首节点】中，如何将这些符合规则的链表后移，其他的保存不变，这里需要注意的是，我们需要跳过链表值为null的节点，因为它已经被遍历完了，所以我们不需要对他进行遍历了。

//找符合条件的节点
    for(int j = 0; j < n; j++){
        if(lists[j] != null){
            int num = lists[j].val; 
            if(num == min){
                //创建节点
                cur.next = new ListNode(num);
                //指针后移
                cur = cur.next;
                //节点后移
                lists[j] = lists[j].next;
            }
        }
    }

最后我们要处理最后一个问题，【对链表数组遍历多少次，才能将每个节点都全部加入到res链表中？？？】

测试用例范围是：

>  *  `k == lists.length`
>  *  `0 <= k <= 10^4`
>  *  `0 <= lists[i].length <= 500`

对于最坏情况，一共由500\*10\*\*4个节点，也就是处理n\*list.length个节点，所以我们需要对这个数据进行精准计算，所以需要循环遍历一遍原始的数组链表

int counter = 0;
    for(ListNode list: lists){
        ListNode temp = list;
        while(temp!=null){
            temp = temp.next;
            counter++;
        }
    }

其实这个counter是当前情况的最坏遍历次数，因为之中，可能存在多个与min相等的节点存在，这样就导致由有些节点已经处理过了**，这是这个解法的一个可以优化的地方**，但是这里我就不做优化处理了，直接放完整代码

public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = new ListNode(0);
        ListNode cur = res;
        int n = lists.length;
        //循环节点个数,每次取第一个节点的值,来进行判断谁加入节点,假如节点等于min,就将节点加入到链表中,然后向后移动一位
        int counter = 0;
        for(ListNode list: lists){
            ListNode temp = list;
            while(temp!=null){
                temp = temp.next;
                counter++;
            }
        }
        for(int i = 0; i < counter; i++){
            int min = Integer.MAX_VALUE;
            for(int j = 0; j < n; j++){
                if(lists[j] != null){
                    //获取最小值
                    min = Math.min(min,lists[j].val);
                }
            }
            //找符合条件的节点
            for(int j = 0; j < n; j++){
                if(lists[j] != null){
                    int num = lists[j].val; 
                    if(num == min){
                        //创建节点
                        cur.next = new ListNode(num);
                        //指针后移
                        cur = cur.next;
                        //节点后移
                        lists[j] = lists[j].next;
                    }
                }
            }
        }
        return res.next;
    }

效率：（确实慢了）

![83399532292240a2a405bcc3fa51124a.png][]

#### 解法二： ####

解法二是基于【合并两个排序链表】的解法二实现的：其思想很简单，四个字，化繁为简，既然你是多个链表，我就取两条出来单独处理，这两条组成的新链表，然后重新取一条链表进行合并处理，这样就把**多链表问题又化为了双链表问题。**直接放代码（合并操作一模一样，只是需要遍历数组链表来不断调用合并函数）

// 基本思路和合并两个链表的一样,因为是多个链表,所以我们化繁为简
    // 两条链表合并为一条新链表然后和另一条链表进行合并操作
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for(ListNode list: lists){
            ans = mergeTwoLists(ans,list);
        }
        return ans;
    }
    //实现合并函数
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null || list2 == null){
            return list1 == null?list2:list1;
        }
        ListNode head = list1.val<=list2.val?list1:list2;
        // cur1指向头,方便确认cur2的指向
        ListNode cur1 = head;
        // 判断节点为1,还是2,如果为1,就让cur2 指向2,如果为2,就指向1,
        ListNode cur2 = head==list1? list2:list1;
        ListNode pre = head;
        cur1 = head.next;
        while(cur1 != null && cur2 != null){
            if(cur1.val<=cur2.val){
                pre.next = cur1;
                cur1 = cur1.next;
            }else if(cur1.val > cur2.val){
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        pre.next = cur1 != null? cur1 : cur2!= null?cur2:null;
        return head;
    }

感谢阅读owo

声明：本文章仅作为学习笔记使用

[21. _ - _LeetCode]: https://leetcode.cn/problems/merge-two-sorted-lists/
[23. _K_ - _LeetCode]: https://leetcode.cn/problems/merge-k-sorted-lists/
[24ec334c8b8200740378119441f98698.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/87c2b6099a8d4a3c9f6899bb65edbe62.jpeg
[94f5215cd855414ab3aa2f4f64fd116b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a895e9a149d7433b96abb78ec4d8800d.png
[86072d422754454a99b19a1a36140784.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f88b509aa00f4bb191ba06950939e4a5.png
[b8b86f55336b46c89aafdfd434f1a8a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/51badffda1fa4e03b4081e08ca6ffa0f.png
[268a7cbf47be4697ae6301551801b5c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f60150865b8f4b2f81ccd3bde8049de7.png
[83399532292240a2a405bcc3fa51124a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d9c4f4cadaaa41bb9ec27e639e9fdb2a.png