23.md

title	date
23. 合并K个排序链表	2020-03-20T00:52:00.000Z

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

解法一：

    /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func mergeKLists(lists []*ListNode) *ListNode {
        var head *ListNode
        
        return _mergeKLists(head, lists)
    }
    
    func _mergeKLists(head *ListNode, lists []*ListNode) (res *ListNode) {
        if len(lists) == 0 {
            return
        }
        var minNode *ListNode
        var minNodeIndex int
        for i, list := range lists {
            if list == nil {
                continue
            }
            if minNode == nil || minNode.Val > list.Val {
                minNode = list
                minNodeIndex = i
            }
        }
        if head == nil {
            head = minNode
            res = head
        } else {
            head.Next = minNode
            head = head.Next
        }
        if minNode != nil {
            lists[minNodeIndex] = lists[minNodeIndex].Next
            _mergeKLists(head, lists)
        }
        return res
    }

这种方法，每次遍历找出列表中最小的链表头，将其加入到新链表中，并重复此过程，直到所有链表都遍历完。

假设列表长度为 n，链表长度为 m，则时间复杂度为 O(n * m)

解法二：

    /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func mergeKLists(lists []*ListNode) *ListNode {
        if len(lists) == 0 {
            return nil
        } else if len(lists) == 1 {
            return lists[0]
        } else if len(lists) == 2 {
            return mergeTwoLists(lists[0], lists[1])
        } else {
            half := len(lists) / 2
            return mergeKLists([]*ListNode{mergeKLists(lists[:half]), mergeKLists(lists[half:])})
        }
    }
    
    
    func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
        if l1 == nil {
            return l2
        }
        if l2 == nil {
            return l1
        }
        var res *ListNode
        if l1.Val < l2.Val {
            res = &ListNode{
                Val: l1.Val,
            }
            l1 = l1.Next
        } else {
            res = &ListNode{
                Val: l2.Val,
            }
            l2 = l2.Next
        }
        head := res
        for l1 != nil && l2 != nil {
            if l1.Val < l2.Val {
                res.Next = &ListNode{
                    Val: l1.Val,
                }
                l1 = l1.Next
            } else {
                res.Next = &ListNode{
                    Val: l2.Val,
                }
                l2 = l2.Next
            }
            res = res.Next
        }
        if l1 == nil {
            res.Next = l2
        } else {
            res.Next = l1
        }
        return head
    }

这种方法，基于合并两个有序链表来完成。