Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
func mergeKLists(lists []*ListNode) *ListNode {
if lists==nil||len(lists)==0{
return nil
}
if len(lists)==1{
return lists[0]
}
var head*ListNode
var p *ListNode
tmp:=mergeKLists(lists[1:])
p0:=tmp
p1:=lists[0]
for p0!=nil&&p1!=nil{
if p0.Val<p1.Val{
if head ==nil{
head=p0
p=p0
p0=p0.Next
}else {
p.Next=p0
p=p0
p0=p0.Next
}
}else {
if head ==nil{
head =p1
p=p1
p1=p1.Next
}else{
p.Next=p1
p=p1
p1=p1.Next
}
}
}
if p0!=nil{
if head ==nil{
head=p0
}else{
p.Next=p0
p0=p0.Next
}
}
if p1!=nil{
if head==nil{
head=p1
}else {
p.Next=p1
}
}
return head
}