Merge k Sorted Lists
解题思路
链表两两合并，分而治之
代码-GoLang
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
p := list1
q := list2
var head, cur *ListNode
var v int
for p != nil || q != nil {
if p == nil {
v = q.Val
q = q.Next
} else if q == nil {
v = p.Val
p = p.Next
} else {
if q.Val < p. Val {
v = q.Val
q = q.Next
} else {
v = p.Val
p = p.Next
}
}
if head == nil {
head = &ListNode{
Val:v,
Next:nil,
}
cur = head
} else {
cur.Next = &ListNode{
Val:v,
Next:nil,
}
cur = cur.Next
}
}
return head
}
func merge(lists []*ListNode, st, en int) *ListNode {
if st == en {
return lists[st]
}
mid := st + (en - st + 1) / 2
l1 := merge(lists, st, mid - 1)
l2 := merge(lists, mid, en)
return mergeTwoLists(l1, l2)
}
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
return merge(lists, 0, len(lists) - 1)
}
