Merge k Sorted Lists

Description

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

将k个有序链表合并为一个链表

Solution

前面刚做了两条链表的合并Merge Two Sorted Lists。

既然两个的合并都做了，k个还会难吗？

显然，将k个链表两两合一即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    res := lists[0]

    for i := 1; i < len(lists); i++ {
        res = mergeTwoLists(res, lists[i])
    }

    return res
}

Similar Problem