23. Merge k Sorted Lists

Hard

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

• k == lists.length

• 0 <= k <= 10^4

• 0 <= lists[i].length <= 500

• -10^4 <= lists[i][j] <= 10^4

• lists[i] is sorted in ascending order.

• The sum of lists[i].length will not exceed 10^4.

解題

第一個方法：使用暴力解

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    nodes := make([]int, 0)

    for _, list := range lists {
       for list != nil {
           nodes = append(nodes, list.Val)
           list = list.Next
       }     
    }

    sort.Ints(nodes)
    ans := &ListNode{}
    head := ans
    for _, n := range nodes {
        ans.Next = &ListNode{ Val: n, Next: nil }
        ans = ans.Next
    }

    return head.Next
}

Divide & Conquer

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 { return nil }

    return helper(lists, 0, len(lists) - 1)
}

func helper(lists []*ListNode, start, end int) *ListNode {
    if start > end { return nil }
    if start == end { return lists[start] }

    mid := start + (end-start)/2
    left := helper(lists, start, mid);
    right := helper(lists, mid + 1, end);

    return merge(left, right)
}

func merge(head1 *ListNode, head2 *ListNode) *ListNode {
    res := &ListNode{ Val:-1 }
    tail := res

    for head1 != nil && head2 != nil {
        if head1.Val < head2.Val {
            tail.Next = head1
            head1 = head1.Next
        } else {
            tail.Next = head2
            head2 = head2.Next
        }
        tail = tail.Next
    }

    if head1 != nil {
        tail.Next = head1
    } 
    if head2 != nil {
        tail.Next = head2
    }

    return res.Next
}