leetcode题目23. 合并K个排序链表（java）

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

解题思路

分而治之，链表两两合并

代码

public ListNode mergeKLists(ListNode[] lists){
    if (lists.length == 0) {
        return null;
    }
    return merge(lists, 0, lists.length - 1);
}

public ListNode merge(ListNode[] lists, int left, int right){
    if (left == right) {
        return lists[left];
    }
    int middle = left + (right - left) / 2;
    ListNode l1 = merge(lists, left, middle);
    ListNode l2 = merge(lists, middle + 1, right);
    return mergeTwoLists(l1, l2);
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    ListNode newHead = null;
    if (l1.val < l2.val) {
        newHead = l1;
        l1 = l1.next;
    } else {
        newHead = l2;
        l2 = l2.next;
    }
    ListNode cur = newHead;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }

    if (l1 != null) {
        cur.next = l1;
    } else if (l2 != null) {
        cur.next = l2;
    }
    return newHead;
}