合并两个有序链表「变题」

21. 合并两个有序链表

简单题复杂做，下面给出两种写法：迭代、递归

// 迭代
// 时间复杂度 : O(m + n)
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    ListNode l1 = list1, l2 = list2;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }
    if (l1 == null) p.next = l2;
    else p.next = l1;
    return dummy.next;
}

// 递归
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null && list2 == null) return null;
    if (list1 == null || list2 == null) return list1 == null ? list2 : list1;
    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

变题一：考虑去重

方法：和合并好的最后一个元素比较。如果相等，跳过；否则，合并

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode p1 = list1, p2 = list2;
    ListNode dummy = new ListNode(-1000);
    ListNode p = dummy;
    while (p1 != null && p2 != null) {
        if (p1.val <= p2.val) {
            // 和前一个元素比较
            if (p.val != p1.val) {
                p.next = p1;
                p = p.next;
            }
            p1 = p1.next;
        } else {
            // 和前一个元素比较
            if (p.val != p2.val) {
                p.next = p2;
                p = p.next;
            }
            p2 = p2.next;
        }
    }
    while (p1 != null) {
        // 和前一个元素比较
        if (p.val != p1.val) {
            p.next = p1;
            p = p.next;
        }
        p1 = p1.next;
    }
    while (p2 != null) {
        // 和前一个元素比较
        if (p.val != p2.val) {
            p.next = p2;
            p = p.next;
        }
        p2 = p2.next;
    }
    return dummy.next;
}

变题二：合并 K 个升序链表

可见题目 合并K个升序链表

// 两两合并
// 时间复杂度 : O(k^2n) -> n + 2n + 3n + ... + kn = (1 + k) * k / 2
// 空间复杂度 : O(1)
public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    if (lists.length == 1) return lists[0];
    ListNode h = lists[0];
    for (int i = 1; i < lists.length; i++) {
        // mergeTwoLists() 见合并两个链表
        h = mergeTwoLists(h, lists[i]);
    }
    return h;
}

// 归并排序的思路
// 时间复杂度 : O(nklogk) -> 每一层合并需要 O(nk)，递归树的高度为 O(logk)
// 空间复杂度 : 递归使用 O(logk) 栈空间
public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    if (lists.length == 1) return lists[0];
    return sort(lists, 0, lists.length - 1);
}
private ListNode sort(ListNode[] lists, int lo, int hi) {
    if (lo == hi) return lists[lo];
    int mid = lo + hi >> 1;
    ListNode left = sort(lists, lo, mid);
    ListNode right = sort(lists, mid + 1, hi);
    // mergeTwoLists() 见合并两个链表
    return mergeTwoLists(left, right);
}

// 利用优先队列
// 时间复杂度 : O(nklogk) -> offer() 操作时间复杂度为 O(logk)
// 空间复杂度 : O(k)
public ListNode mergeKLists(ListNode[] lists) {
    Queue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode list : lists) {
        if (list != null) {
            q.offer(list);
        }
    }
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    while (!q.isEmpty()) {
        ListNode cur = q.poll();
        p.next = cur;
        p = p.next;
        if (cur.next != null) q.offer(cur.next);
    }
    return dummy.next;
}