图片.png

    图片.png
    优先队列或者进行排序

    1. package main
    3. import (
    4.     "container/heap"
    5.     "fmt"
    6.     "sort"
    7. )
    9. type ListNode struct {
    10.     Val  int
    11.     Next *ListNode
    12. }
    13. type NodeSlice []*ListNode
    15. func (p NodeSlice) Len() int           { return len(p) }
    16. func (p NodeSlice) Less(i, j int) bool { return p[i].Val < p[j].Val }
    17. func (p NodeSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
    19. func (p *NodeSlice) Push(x interface{}) {
    20.     node := x.(*ListNode)
    21.     *p = append(*p, node)
    22. }
    23. func (p *NodeSlice) Pop() interface{} {
    24.     old := *p
    25.     n := len(old)
    26.     item := old[n-1]
    27.     *p = old[0 : n-1]
    28.     return item
    29. }
    30. func mergeKLists(lists []*ListNode) *ListNode {
    31.     dummyHead := &ListNode{
    32.         Val:  -1,
    33.         Next: nil,
    34.     }
    35.     curr := dummyHead
    36.     nodeList := make(NodeSlice, 0)
    37.     for i := range lists {
    38.         if lists[i] != nil {
    39.             nodeList = append(nodeList, lists[i])
    40.         }
    41.     }
    42.     heap.Init(&nodeList)
    43.     for len(nodeList) > 0 {
    44.         item := heap.Pop(&nodeList).(*ListNode)// 最小元素
    45.         next := item.Next
    46.         item.Next = nil
    47.         curr.Next = item
    48.         curr = item
    49.         if next != nil {
    50.             heap.Push(&nodeList, next)
    51.         }
    52.     }
    53.     return dummyHead.Next
    54. }
    56. func mergeKLists1(lists []*ListNode) *ListNode {
    57.     dummyHead := &ListNode{
    58.         Val:  -1,
    59.         Next: nil,
    60.     }
    61.     nodeList := make(NodeSlice, 0)
    62.     for i := range lists {
    63.         h :=lists[i]
    64.         for h!= nil {
    65.             nodeList = append(nodeList, h)
    66.             h=h.Next
    67.         }
    68.     }
    69.     sort.Sort(nodeList)
    70.     curr := dummyHead
    71.     for _,v :=range nodeList{
    72.         curr.Next = v
    73.         curr = v
    74.     }
    75.     return dummyHead.Next
    76. }
    80. func main() {
    81.     a1 :=ListNode{Val:  1,}
    82.     b1 :=&ListNode{Val: 4,}
    83.     a1.Next = b1
    84.     c1 :=ListNode{Val:  5,}
    85.     b1.Next =&c1
    86.     a2 :=ListNode{Val:  1,}
    87.     b2 :=ListNode{Val:  3,}
    88.     a2.Next = &b2
    89.     c2 :=ListNode{Val:  4,}
    90.     b2.Next =&c2
    91.     a3 :=ListNode{Val:  2,}
    92.     b3 :=ListNode{Val:  6,}
    93.     a3.Next =&b3
    94.     r := mergeKLists([]*ListNode{&a1,&a2,&a3,nil})
    95.     for r!= nil{
    96.         fmt.Println(r.Val)
    97.         r = r.Next
    98.     }
    99. }

    // [[-6,-4,0,0,4],[],[-4,-2,-1,1,2,3],[-9,-6,-5,-2,4,4],[-9,-6,-5,-2,-1,3],[-2,-1,0],[-6],[-8,-1,0,2]]