链表oj-----＞合并k个有序链表

朴灿烈づ我的快乐病毒、 2023-10-02 15:33 12阅读 0赞

**题目内容：**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]

**解题思路：**

>  *  **合并k个有序链表的本质是首先可以合并两个有序有序链表**
>  *  **如何合并两个有序链表：**
> 
> 1.  **新创建一个链表（为什么不能在原有的链表上进行更改，首先，链表长度不满足，其次，当更改一个其中的一个指向时，往后的结点已经丢失）**
> 2.  **新创建的链表的指向只根据我们的要求去进行改变的**
> 3.  **用这个方法合并时，必然会有一个链表至少有一个结点没有指向，所以，在循环结束后，需要对还没有指向空的链表继续进行连接**
> 4.  **返回我们定义的链表就是合并后的新链表**
> 
>  *  **此时，合并k个升序链表就简单多了，我们只需用考虑，怎么才能让其连续合并，那就是利用循环，不断的更新我们定义的链表，就可以了**

**解题代码：**

class Solution {
        //编写合并升序链表的方法
        public ListNode mergeTwoLists(ListNode l1,ListNode l2){
            //对两个头结点进行判断
            if(l1 == null){
                return l2;
            }
            if(l2 == null){
                return l1;
            }
    
            ListNode newNode = new ListNode(0);
            ListNode node = newNode;
    
            ListNode cur1 = l1;
            ListNode cur2 = l2;
    
            while(cur1 != null && cur2 != null){
                if(cur1.val < cur2.val){
                    node.next = cur1;
                    cur1 = cur1.next;
                }else{
                    node.next = cur2;
                    cur2 = cur2.next;
                }
                
                node = node.next;
            }
    
            if(cur1 == null){
                node.next = cur2;
            }
            if(cur2 == null){
                node.next = cur1;
            }
    
            return newNode.next;
        }
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists == null){
                return null;
            }
    
            ListNode node = null;
            for(int i = 0;i < lists.length;i++){
                node = mergeTwoLists(node,lists[i]);
            }
            return node;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/82010ceb32c4424b80d0e34109df9764.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16