13.合并 K 个升序链表

• 3.9

  • 辅助函数添加数组的左右指针进去，然后返回的时具体的 list 链表

• 2.11

  • 在12.链表排序的基础上，变成了数组的分割，因为要加上左右边界给递归，所以需要辅助函数 divide

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length==0) return null;
        return divide(lists,0,lists.length-1);
    }
    public ListNode divide(ListNode[] lists,int left,int right){
        if(left==right) return lists[left];
 
        int mid = (left+right)/2;
        ListNode l =  divide(lists,left,mid);
        ListNode r =  divide(lists,mid+1,right);
 
        return merge(l,r);
    }
    public ListNode merge(ListNode l,ListNode r){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l!=null&&r!=null){
            if(l.val<r.val){
                cur.next = l;
                l = l.next;
            }else{
                cur.next = r;
                r = r.next;
            }
            cur = cur.next;
        }
        cur.next = (l==null)?r:l;
        return dummy.next;
    }
    
}

• 1.24
  • 就是类似于合并链表，只不过分割的是数组
  • 注意递归结束条件

class Solution {
    // 1. 主函数：处理边界，开启分治
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return divideAndConquer(lists, 0, lists.length - 1);
    }
 
    // 2. 分治函数：像切蛋糕一样把数组一分为二，直到只剩一个链表
    private ListNode divideAndConquer(ListNode[] lists, int left, int right) {
        // 递归终止条件：只剩一个链表了，不用合了，直接返回
        if (left == right) {
            return lists[left];
        }
 
        // 找中点，分两半
        int mid = left + (right - left) / 2;
        
        // 左边合并好的链表
        ListNode l1 = divideAndConquer(lists, left, mid);
        // 右边合并好的链表
        ListNode l2 = divideAndConquer(lists, mid + 1, right);
        
        // 把左右两部分合并
        return mergeTwoLists(l1, l2);
    }
 
    // 3. 基础函数：合并两个有序链表 (你刚才已经写出完美版的代码)
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
 
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}