LinkedList - 23. Merge k Sorted Lists

23. Merge k Sorted Lists

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

Example:

Input:
[
1->4->5,
1->3->4,
2->6
> ]
Output: 1->1->2->3->4->4->5->6

思路：

合并k个有序链表，采用分治的思想，递归合并完左边，右边，在最后进行合并，递归出口就是只有一条链表的时候，时间复杂度O(nlogk)。

代码：

golang:

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

func merge(lists []*ListNode, left, right int) *ListNode {
    if left == right {
        return lists[left]
    }
    
    // 二分
    mid := (right - left ) / 2 + left
    l := merge(lists, left, mid)
    r := merge(lists, mid+1, right)
    
    var dummy = &ListNode{}
    var cur = dummy
    
    for l != nil && r != nil {
        if l.Val < r.Val {
            cur.Next = l
            l = l.Next
        } else {
            cur.Next = r
            r = r.Next
        }
        cur = cur.Next
    }
    
    if l != nil {
        cur.Next = l
    }
    if r != nil {
        cur.Next = r
    }
    
    return dummy.Next
}

/**

 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;
        return helper(lists, 0, lists.length - 1);
    }
    
    private ListNode helper(ListNode[] lists, int start, int end) {
        if (start == end) return lists[start];
        
        int mid = (end - start) / 2 + start;
        ListNode first = helper(lists, start, mid);
        ListNode second = helper(lists, mid + 1, end);
        
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (first != null && second != null) {
            if (first.val < second.val) {
                cur.next = first;
                first = first.next;
            } else {
                cur.next = second;
                second = second.next;
            }
            cur = cur.next;
        }
        if (first == null) 
            cur.next = second;
        if (second == null)
            cur.next = first;
        
        return head.next;
    }
}