继续打卡算法题,今天学习的是LeetCode的第23题合并K个升序链表,这道题目是道hard题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些帮助。
哈哈,今天挑战第一道hard题,之前已经学习过合并两个有序链表 ,今天这题是它的升级plus版本
分析一波题目
因为两个有序链表我们可以合并,那么合并k个我们可以采用分而治之的思想解决。
第一次合并k个中的两个,然后将合并的结果和k个中的下一个进行合并,依次类推。
编码解决
/**
* 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;
}
}
总结
分而治之思想
也是一个常用解题技巧,如果指定子问题可以求解,原问题分解成多个子问题求解,再合并结果。