LeetCode第23题合并 K 个升序链表

简介: 这篇文章介绍了LeetCode第23题"合并K个升序链表"的解题方法,使用分而治之的思想,通过递归合并链表的方式解决了这个难题。

继续打卡算法题,今天学习的是LeetCode的第23题合并K个升序链表,这道题目是道hard题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些帮助。

image.png

哈哈,今天挑战第一道hard题,之前已经学习过合并两个有序链表 ,今天这题是它的升级plus版本

分析一波题目

因为两个有序链表我们可以合并,那么合并k个我们可以采用分而治之的思想解决。

第一次合并k个中的两个,然后将合并的结果和k个中的下一个进行合并,依次类推。

WechatIMG422.jpg

编码解决

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
   
   
    public ListNode mergeKLists(ListNode[] lists) {
   
   

        if(lists == null || lists.length == 0) {
   
   
            return null;
        }

        if( lists.length == 1) {
   
   
            return lists[0];
        }

        //递归 每次合并两个数组, 最后剩下0个链表
        ListNode list= lists[0];
        for(int i= 1; i< lists.length; i++) {
   
   
            list = merge2Lists(list, lists[i]);
        }    
        return list;

    }

    //递归 每次合并两个数组, 最后剩下0个链表
    public ListNode merge2Lists(ListNode list1 , ListNode list2) {
   
   

            //list1已经到到尾部 递归结束
            if(list1 == null ) {
   
   
                return list2;
            }
            //list2已经到到尾部
            if(list2 == null) {
   
   
                return list1;
            }

            if(list1.val < list2.val) {
   
   
                //递归
                list1.next = merge2Lists(list1.next, list2);
                return list1;
            }
            //递归
            list2.next = merge2Lists(list1, list2.next);
            return list2;
    }
}

总结

分而治之思想也是一个常用解题技巧,如果指定子问题可以求解,原问题分解成多个子问题求解,再合并结果。

相关文章
|
2月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
2月前
|
存储 算法
LeetCode第86题分隔链表
文章介绍了LeetCode第86题"分隔链表"的解法,通过创建两个新链表分别存储小于和大于等于给定值x的节点,然后合并这两个链表来解决问题,提供了一种简单易懂且操作原链表的解决方案。
LeetCode第86题分隔链表
|
2月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
2月前
|
C++ 索引
leetcode 707.设计链表
本文提供了解决LeetCode 707题"设计链表"的C++实现,包括单链表的节点定义和类方法实现,如添加节点、获取节点值、删除节点等。
|
2月前
|
算法
LeetCode第92题反转链表 II
文章分享了LeetCode第92题"反转链表 II"的解法,通过使用四个指针来记录和更新反转链表段的头部、尾部以及前一个和后一个节点,提供了一种清晰且易于理解的解决方案。
LeetCode第92题反转链表 II
|
2月前
|
算法
LeetCode第21题合并两个有序链表
该文章介绍了 LeetCode 第 21 题合并两个有序链表的解法,通过创建新链表,依次比较两个链表的头节点值,将较小的值插入新链表,直至其中一个链表遍历完,再将另一个链表剩余部分接到新链表后面,实现合并。
LeetCode第21题合并两个有序链表
|
2月前
|
算法
LeetCode第19题删除链表的倒数第 N 个结点
该文章介绍了 LeetCode 第 19 题删除链表的倒数第 N 个结点的解法,通过使用快慢双指针,先将快指针移动 n 步,然后快慢指针一起遍历,直到快指针到达链尾,从而找到倒数第 N 个结点的前一个结点进行删除,同时总结了快慢指针可减少链表遍历次数的特点。
LeetCode第19题删除链表的倒数第 N 个结点
|
2月前
|
存储 算法 Python
【面试题】合井K个升序链表
【面试题】合井K个升序链表
31 0
|
2月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
47 0
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表