23. 合并K个排序链表

https://leetcode-cn.com/problems/merge-k-sorted-lists/

问题描述

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

示例:

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

解题思路

普通方法

ListNode *mergeKLists(vector<ListNode *> &lists) {
    int length = lists.size();
    if (length == 2) {
        return mergeTwoLists(lists[0], lists[1]);
    } else {
        int newLength = length / 2;
        if (length % 2 == 1) {
            newLength++;
        }
        vector<ListNode *> newLists(newLength);
        for (int i = 0; i < newLength - 1; i++) {
            newLists[i] = mergeTwoLists(lists[2 * i], lists[2 * i + 1]);
        }
        if (length % 2 == 1) {
            newLists[newLength - 1] = lists[2 * newLength - 2];
        }
        return mergeKLists(newLists);
    }
}

对所有链表两两分组，依次执行二路归并，再将所有结果收集起来，建立一个新的向量，递归地执行方法。本地执行成功，提交代码后出现栈溢出的错误。

AddressSanitizer:DEADLYSIGNAL
=================================================================
==29==ERROR: AddressSanitizer: stack-overflow on address 0x7ffc216d7ff8 (pc 0x00000040b6c4 bp 0x7ffc216d8170 sp 0x7ffc216d8000 T0)
==29==ABORTING

栈溢出

ListNode *mergeKLists(vector<ListNode *> &lists) {
    int length = lists.size();
    if (length == 0) {
        return nullptr;
    } else if (length == 1) {
        return lists[0];
    } else if (length == 2) {
        return mergeTwoLists(lists[0], lists[1]);
    } else {
        int newLength = length / 2;
        if (length % 2 == 1) {
            newLength++;
        }
        vector<ListNode *> newLists(newLength);
        for (int i = 0; i < newLength - 1; i++) {
            newLists[i] = mergeTwoLists(lists[2 * i], lists[2 * i + 1]);
        }
        if (length % 2 == 1) {
            newLists[newLength - 1] = lists[2 * newLength - 2];
        }
        return mergeKLists(newLists);
    }
}

解决向量长度为 0 或 1 时无限递归问题。

判断循环次数

ListNode *mergeKLists(vector<ListNode *> &lists) {
    int length = lists.size();
    if (length == 0) {
        return nullptr;
    } else if (length == 1) {
        return lists[0];
    } else if (length == 2) {
        return mergeTwoLists(lists[0], lists[1]);
    } else {
        int newLength = length / 2;
        if (length % 2 == 1) {
            newLength++;
            vector<ListNode *> newLists(newLength);
            for (int i = 0; i < newLength - 1; i++) {
                newLists[i] = mergeTwoLists(lists[2 * i], lists[2 * i + 1]);
            }
            newLists[newLength - 1] = lists[2 * newLength - 2];
            return mergeKLists(newLists);
        } else {
            vector<ListNode *> newLists(newLength);
            for (int i = 0; i < newLength; i++) {
                newLists[i] = mergeTwoLists(lists[2 * i], lists[2 * i + 1]);
            }
            return mergeKLists(newLists);
        }
    }
}

分组后是否产生余数对循环次数有不同的影响。