《零基础Go语言算法实战》【题目 4-7】实现链表的排序
《零基础Go语言算法实战》
【题目 4-7】实现链表的排序
请用 Go 语言实现合并 K 个排序的链表并将其作为一个排序链表返回。
【解答】
① 思路。
借助分治算法的思想，递归对比两个链表中的每个元素的值的大小，然后将 K 个有序链
表两两合并即可。
② Go 语言实现。
package main
import "fmt"
// 定义单链表
type ListNode struct {
Data int
Next *ListNode
}
// 合并 K 个链表
func mergeKLists(lists []*ListNode) *ListNode {
length := len(lists)
if length < 1 {
return nil
}
if length == 1 {
return lists[0]
}
num := length / 2
left := mergeKLists(lists[:num])
right := mergeKLists(lists[num:])
return mergeTwoLists(left, right)
}
// 合并两个链表
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
if l1.Data < l2.Data {
l1.Next = mergeTwoLists(l1.Next, l2)
return l1
}
l2.Next = mergeTwoLists(l1, l2.Next)
return l2
}
func main() {
nodeList1 := ListNode{66, nil}
nodeList2 := ListNode{99, nil}
nodeList3 := ListNode{88, nil}
nodeList4 := ListNode{55, nil}
ListsK := []*ListNode{&nodeList1, &nodeList2, &nodeList3, &nodeList4}
ret := mergeKLists(ListsK)
// 打印结果
fmt.Println(ret.Data)
if ret.Next != nil {
fmt.Println(ret.Next.Data)
if ret.Next.Next != nil {
fmt.Println(ret.Next.Next.Data)
if ret.Next.Next.Next != nil {
fmt.Println(ret.Next.Next.Next.Data)
}
}
}
}
//$ go run interview4-7.go
//55
//66
//88
//99