【重点】23.合并K个升序链表

题目

法1：分治合并

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l > r) {
            return null;
        }
        if (l == r) {
            return lists[l];
        }
        int mid = l + (r - l) / 2;
        return merge2List(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode merge2List(ListNode first, ListNode second) {
        ListNode dummy = new ListNode(-1);
        ListNode tmp = dummy;
        while (first != null && second != null) {
            if (first.val <= second.val) {
                tmp.next = first;
                first = first.next;
            } else {
                tmp.next = second;
                second = second.next;
            }
            tmp = tmp.next;
        }
        if (first == null) {
            tmp.next = second;
        }
        if (second == null) {
            tmp.next = first;
        }

        return dummy.next;
    }
}

法2：其他

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        ListNode merged = lists[0];
        for (int i = 1; i < lists.length; ++i) {
            merged = merge(merged, lists[i]);
        }

        return merged;
    }

    public ListNode merge(ListNode first, ListNode second) {
        ListNode dummy = new ListNode(-1);
        ListNode tmp = dummy;
        while (first != null && second != null) {
            if (first.val <= second.val) {
                tmp.next = first;
                first = first.next;
            } else {
                tmp.next = second;
                second = second.next;
            }
            tmp = tmp.next;
        }
        if (first == null) {
            tmp.next = second;
        }
        if (second == null) {
            tmp.next = first;
        }

        return dummy.next;
    }
}