Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
148题解决的是2个链表的有序合并，这里是k个～～可以利用之前148题的Merge函数。我们利用分治思想，将k个链表，分成左右两部分分别进行递归合并～
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
length := len(lists)
half := length / 2
if length == 1 {
return lists[0]
}
if length == 2 {
l0, l1 := lists[0], lists[1]
if l0 == nil {
return l1
}
if l1 == nil {
return l0
}
return merge(l0, l1)
}
return mergeKLists([]*ListNode{mergeKLists(lists[half:]), mergeKLists(lists[:half])})
}
func merge(left, right *ListNode) *ListNode {
node := &ListNode{}
//node会随着新节点的插入一直往后递增
head := node
for left != nil && right != nil {
if left.Val < right.Val {
node.Next, left = left, left.Next
} else {
node.Next, right = right, right.Next
}
node = node.Next
}
//如果只剩left或者right
if left != nil {
node.Next = left
} else {
node.Next = right
}
return head.Next
}
网友评论