23. 合并 K 个升序链表 #
题目地址 #
解题思路 #
具体实现 #
```go
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
n := len(lists)
return merge(lists, 0, n-1)
}
func merge(lists []*ListNode, left, right int) *ListNode {
if left == right {
return lists[left]
}
mid := left + (right-left)/2
l1 := merge(lists, left, mid)
l2 := merge(lists, mid+1, right)
return mergeTwoLists(l1, l2)
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
if l1.Val < l2.Val {
l1.Next = mergeTwoLists(l1.Next, l2)
return l1
} else {
l2.Next = mergeTwoLists(l1, l2.Next)
return l2
}
}
func main() {
list1 := &ListNode{Val: 1, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}
list2 := &ListNode{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}}
list3 := &ListNode{Val: 2, Next: &ListNode{Val: 6}}
lists := []*ListNode{list1, list2, list3}
result := mergeKLists(lists)
for result != nil {
fmt.Printf("%d ", result.Val)
result = result.Next
}
}
```