题解 | #合并k个已排序的链表#
合并k个已排序的链表
http://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
package main
func mergeKLists( lists []*ListNode ) *ListNode {
n := len(lists)
if n == 0 {
return nil
}
if n == 1 {
return lists[0] // 递归终点1:
}
if n == 2 {
return merge(lists[0], lists[1]) // 递归终点2：合并两条链表
}
tmp := n / 2
return merge(mergeKLists(lists[:tmp]), mergeKLists(lists[tmp:])) //递归，数组拆两半
}
func merge(list1, list2 *ListNode) *ListNode {
h := &ListNode{}
ret := h
for ;list1 != nil && list2 != nil; {
if list1.Val < list2.Val {
h.Next = list1
list1 = list1.Next
} else {
h.Next = list2
list2 = list2.Next
}
h = h.Next
}
if list1 == nil {
h.Next = list2
}
if list2 == nil {
h.Next = list1
}
return ret.Next
}
阿里云工作强度 731人发布