147 lines
2.4 KiB
Go
147 lines
2.4 KiB
Go
package top100liked
|
|
|
|
import (
|
|
"fmt"
|
|
"testing"
|
|
)
|
|
|
|
// https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked
|
|
|
|
type ListNode struct {
|
|
Val int
|
|
Next *ListNode
|
|
}
|
|
|
|
// 暴力解，非常慢，但是能通过
|
|
// func mergeKLists(lists []*ListNode) *ListNode {
|
|
// if lists == nil {
|
|
// return nil
|
|
// }
|
|
// dummy := &ListNode{}
|
|
// p := dummy
|
|
// var minValue int
|
|
// minIndex := -1
|
|
// for {
|
|
// for i := range lists {
|
|
// if lists[i] != nil {
|
|
// if minIndex == -1 {
|
|
// minValue = lists[i].Val
|
|
// minIndex = i
|
|
// }
|
|
// if lists[i].Val < minValue {
|
|
// minValue = lists[i].Val
|
|
// minIndex = i
|
|
// }
|
|
// }
|
|
// }
|
|
// if minIndex == -1 {
|
|
// return nil
|
|
// }
|
|
// p.Next = lists[minIndex]
|
|
// p = p.Next
|
|
// lists[minIndex] = lists[minIndex].Next
|
|
// minIndex = -1
|
|
// allNil := true
|
|
// for i := range lists {
|
|
// if lists[i] != nil {
|
|
// allNil = false
|
|
// break
|
|
// }
|
|
// }
|
|
// if allNil {
|
|
// break
|
|
// }
|
|
// }
|
|
// return dummy.Next
|
|
// }
|
|
|
|
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
|
|
p1, p2 := list1, list2
|
|
p := &ListNode{}
|
|
res := p
|
|
for p1 != nil && p2 != nil {
|
|
if p1.Val <= p2.Val {
|
|
p.Next = p1
|
|
p = p.Next
|
|
p1 = p1.Next
|
|
} else {
|
|
p.Next = p2
|
|
p = p.Next
|
|
p2 = p2.Next
|
|
}
|
|
}
|
|
for p1 != nil {
|
|
p.Next = p1
|
|
p = p.Next
|
|
p1 = p1.Next
|
|
}
|
|
for p2 != nil {
|
|
p.Next = p2
|
|
p = p.Next
|
|
p2 = p2.Next
|
|
}
|
|
return res.Next
|
|
}
|
|
|
|
// 分治归并
|
|
func mergeKLists(lists []*ListNode) *ListNode {
|
|
if len(lists) == 0 || lists == nil {
|
|
return nil
|
|
}
|
|
if len(lists) == 1 {
|
|
return lists[0]
|
|
}
|
|
l := []*ListNode{}
|
|
for i := range len(lists) / 2 {
|
|
l = append(l, mergeTwoLists(lists[2*i], lists[2*i+1]))
|
|
}
|
|
if len(lists)%2 != 0 {
|
|
l = append(l, lists[len(lists)-1])
|
|
}
|
|
return mergeKLists(l)
|
|
}
|
|
|
|
func Test1(t *testing.T) {
|
|
input := []*ListNode{
|
|
{
|
|
Val: 1,
|
|
Next: &ListNode{
|
|
Val: 4,
|
|
Next: &ListNode{
|
|
Val: 5,
|
|
Next: nil,
|
|
},
|
|
},
|
|
},
|
|
{
|
|
Val: 1,
|
|
Next: &ListNode{
|
|
Val: 3,
|
|
Next: &ListNode{
|
|
Val: 4,
|
|
Next: nil,
|
|
},
|
|
},
|
|
},
|
|
{
|
|
Val: 2,
|
|
Next: &ListNode{
|
|
Val: 6,
|
|
Next: nil,
|
|
},
|
|
},
|
|
}
|
|
output := mergeKLists(input)
|
|
for output != nil {
|
|
fmt.Print(output.Val, " ")
|
|
output = output.Next
|
|
}
|
|
}
|
|
|
|
func Test2(t *testing.T) {
|
|
mergeKLists(nil)
|
|
}
|
|
func Test3(t *testing.T) {
|
|
mergeKLists([]*ListNode{nil})
|
|
}
|