Linked List - Merge k Sorted Lists

by LauCyun Sep 15,2014 23:13:37 4,982 views

Question

Problem Statement

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

Example

Given lists:

[
  2->4->null,
  null,
  -1->null
],

return -1->2->4->null.

题解1 - 选择归并(TLE) 

参考单链表 - 合并两个有序的链表(Merge Two Sorted Lists)中对两个有序链表的合并方法,这里我们也可以采用从 k 个链表中选择其中最小值的节点链接到last->next(和选择排序思路有点类似),同时该节点所在的链表表头节点往后递推一个。直至last遍历完 k 个链表的所有节点,此时表头节点均为NULL, 返回dummy->next.

这种方法非常简单直接,但是时间复杂度较高,容易出现Time Limit Exceeded。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new list node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * Merge k sorted linked lists and return it as one sorted list.
 *
 * eg.
 *   Given lists:
 *   [
 *     2->4->null,
 *     null,
 *     -1->null
 *   ],
 *   return -1->2->4->null.
 *
 * @param lists: K sorted linked lists.
 * @param listsSize: Size of k sorted linked lists.
 * @return: one sorted list
 */
struct ListNode *mergeKLists(struct ListNode **lists, const int listsSize) {
    if (lists == NULL || listsSize == 0) {
        return NULL;
    }

    struct ListNode *dummy = newNode(INT_MAX);
    struct ListNode *last = dummy;

    while (1) {
        int count = 0;
        int index = -1, tempVal = INT_MAX;
        int i = 0;
        for (; i < listsSize; ++i) {
            if (NULL == lists[i]) {
                ++count;
                if (count == listsSize) {
                    last->next = NULL;
                    // do not forget free dummy
                    last = dummy->next;
                    free(dummy);
                    return last;
                }
                continue;
            }

            // choose the min value in non-NULL ListNode
            if (NULL != lists[i] && lists[i]->val <= tempVal) {
                tempVal = lists[i]->val;
                index = i;
            }
        }
        last->next = lists[index];
        last = last->next;
        lists[index] = lists[index]->next;
    }
}

源码分析

  1. 由于头节点不定,我们使用dummy节点。
  2. 使用last表示每次归并后的新链表末尾节点。
  3. count用于累计链表表头节点为NULL的个数,若与 k 相同则代表所有节点均已遍历完。
  4. tempVal用于保存每次比较 lists 中各链表表头节点中的最小值,index保存本轮选择归并过程中最小值对应的链表索引,用于循环结束前递推该链表表头节点。

 复杂度分析

由于每次for循环只能选择出一个最小值,总的时间复杂度最坏情况下为\(O(k⋅\sum_{i=1}^{k} l_i)\)。空间复杂度近似为\(O(1)\)

题解2 - 迭代调用Merge Two Sorted Lists(TLE)

鉴于题解1时间复杂度较高,题解2中我们可以反复利用时间复杂度相对较低的单链表 - 合并两个有序的链表(Merge Two Sorted Lists)。即先合并链表1和2,接着将合并后的新链表再与链表3合并,如此反复直至所有链表均已完全合并。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new list node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * Merge two sorted (ascending) linked lists and return it as a new sorted list.
 *
 * eg.
 *   Given 1->3->8->11->15->null, 2->null , return 1->2->3->8->11->15->null
 *
 * @param l1: sorted linked lists
 * @param l2: sorted linked lists
 * @return: one sorted list
 */
struct ListNode *mergeLists(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode *dummy = newNode(INT_MAX);
    struct ListNode *last = dummy;

    while ((l1 != NULL) && (l2 != NULL)) {
        if (l1->val < l2->val) {
            last->next = l1;
            l1 = l1->next;
        } else {
            last->next = l2;
            l2 = l2->next;
        }
        last = last->next;
    }

    // do not forget this line!
    last->next = (NULL != l1) ? l1 : l2;

    // do not forget free dummy
    last = dummy->next;
    free(dummy);
    return last;
}

/***
 * Merge k sorted linked lists and return it as one sorted list.
 *
 * eg.
 *   Given lists:
 *   [
 *     2->4->null,
 *     null,
 *     -1->null
 *   ],
 *   return -1->2->4->null.
 *
 * @param lists: K sorted linked lists.
 * @param listsSize: Size of k sorted linked lists.
 * @return: one sorted list
 */
struct ListNode *mergeKLists2(struct ListNode **lists, const int listsSize) {
    if (lists == NULL || listsSize == 0) {
        return NULL;
    }

    struct ListNode *dummy = lists[0];

    int i = 1;
    for (; i < listsSize; ++i) {
        dummy = mergeLists(dummy, lists[i]);
    }
    return dummy;
}

源码分析

实现合并两个链表的子方法后就没啥难度了,mergeKLists2中左半部分链表初始化为lists[0], for循环后迭代归并llists[i].

复杂度分析

合并两个链表时最差时间复杂度为\(O(l_1+l_2)\), 那么在以上的实现中总的时间复杂度可近似认为是\((l_1+l_2)+((l_1+l_2)+l_3)...+((((l_1+l_2)+l_3)+...)+l_k)=O(\sum_{i=1}^{k}(k-i) ⋅l_i)\)。比起题解1复杂度是要小一点,但量级上仍然差不太多。实际运行时间也证明了这一点,题解2的运行时间差不多时题解1的一半。那么还有没有进一步降低时间复杂度的可能呢?当然是有的,且看下题分解...

题解3 - 二分调用Merge Two Sorted Lists

题解2中mergeKLists2优化空间不大,那咱们就来看看mergeKLists2中的for循环,仔细观察可得知第i个链表\(l_i\)被遍历了\(listsSize-i\)次,如果我们使用二分法对其进行归并呢?从中间索引处进行二分归并后,每个链表参与合并的次数变为\(\log{k}\), 故总的时间复杂度可降至\(\log{k}⋅\sum_{i=1}^{k}l_{i}\)。优化幅度较大。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *newNode(const int);
struct ListNode *mergeTwoLists(struct ListNode *, struct ListNode *);
struct ListNode *mergeKLists3(struct ListNode **, const int);
struct ListNode *binarySearch(struct ListNode **, const int, const int);

/***
 * Create a new list node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * Merge two sorted (ascending) linked lists and return it as a new sorted list.
 *
 * eg.
 *   Given 1->3->8->11->15->null, 2->null , return 1->2->3->8->11->15->null
 *
 * @param l1: sorted linked lists
 * @param l2: sorted linked lists
 * @return: one sorted list
 */
struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode *dummy = newNode(INT_MAX);
    struct ListNode *last = dummy;

    while ((l1 != NULL) && (l2 != NULL)) {
        if (l1->val < l2->val) {
            last->next = l1;
            l1 = l1->next;
        } else {
            last->next = l2;
            l2 = l2->next;
        }
        last = last->next;
    }

    // do not forget this line!
    last->next = (NULL != l1) ? l1 : l2;

    // do not forget free dummy
    last = dummy->next;
    free(dummy);
    return last;
}

/***
 * Binary Search of linked lists.
 * @param lists: K sorted linked lists.
 * @param start: start
 * @param end: end
 * @return: one sorted list.
 */
struct ListNode *binarySearch(struct ListNode **lists, const int start, const int end) {
    if (start == end) {
        return lists[start];
    } else if (start + 1 == end) {
        return mergeTwoLists(lists[start], lists[end]);
    }

    struct ListNode *left = binarySearch(lists, start, start + (end - start) / 2);
    struct ListNode *right = binarySearch(lists, start + (end - start) / 2 + 1, end);

    return mergeTwoLists(left, right);
}

/***
 * Merge k sorted linked lists and return it as one sorted list.
 *
 * eg.
 *   Given lists:
 *   [
 *     2->4->null,
 *     null,
 *     -1->null
 *   ],
 *   return -1->2->4->null.
 *
 * @param lists: K sorted linked lists.
 * @param listsSize: Size of k sorted linked lists.
 * @return: one sorted list
 */
struct ListNode *mergeKLists3(struct ListNode **lists, const int listsSize) {
    if (lists == NULL || listsSize == 0) {
        return NULL;
    }

    return binarySearch(lists, 0, listsSize - 1);
}

源码分析

由于需要建立二分递归模型,另建一私有方法binarySearch引入起止位置较为方便。下面着重分析binarySearch

  1. 分两种边界条件处理,分别是start == endstart + 1 == end. 虽然第二种边界条件可以略去,但是加上会节省递归调用的栈空间。
  2. 使用分治思想理解binarySearch, leftright的边界处理建议先分析几个简单例子,做到不重不漏。
  3. 注意mergeTwoLists3中传入的参数,为lists[start]而不是start...

mergeKLists3中调用binarySearch时传入的end参数为listsSize-1,而不是listsSize.

复杂度分析

题解中已分析过,最坏的时间复杂度为\(\log{k}⋅\sum_{i=1}^{k}l_{i}\), 空间复杂度近似为\( O(1)\)

优化后的运行时间显著减少!由题解2中的500+ms 减至10ms以内。

Tags