合并k个有序链表——小顶堆&分治

# 小顶堆

```go
type Heap struct {
    store []*ListNode
}

func (h *Heap) Push(val *ListNode) {
    h.store = append(h.store, val)
    h.liftUp(len(h.store)-1)
}

func (h *Heap) liftUp(i int) {
    if i == 0 {
        return
    }
    parent := (i - 1) / 2
    if h.store[parent].Val > h.store[i].Val {
        h.store[parent], h.store[i] = h.store[i], h.store[parent]
        h.liftUp(parent)
    }
}

func (h *Heap) Pop() *ListNode {
    h.store[0], h.store[len(h.store)-1] = h.store[len(h.store)-1], h.store[0]
    ret := h.store[len(h.store)-1]
    h.store = h.store[:len(h.store)-1]
    h.pushDown(0)
    return ret
}

func (h *Heap) pushDown(i int) {
    left := i * 2 + 1
    right := i * 2 + 2
    minIdx := i
    if left < len(h.store) && h.store[minIdx].Val > h.store[left].Val {
        minIdx = left
    }
    if right < len(h.store) && h.store[minIdx].Val > h.store[right].Val {
        minIdx = right
    }
    if minIdx != i {
        h.store[minIdx], h.store[i] = h.store[i], h.store[minIdx]
        h.pushDown(minIdx)
    }
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    heap := Heap{}
    for _, v := range lists {
        if v != nil {
            heap.Push(v)
        }
    }
    dummy := &ListNode{}
    cur := dummy
    for len(heap.store) > 0 {
        cur.Next = heap.Pop()
        cur = cur.Next
        if cur.Next != nil {
            heap.Push(cur.Next)
        }
    }
    return dummy.Next
}
```

# 分治

```go
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    l, r := 0, len(lists)-1
    return merge(lists, l, r)
}

func merge(lists []*ListNode, left, right int) *ListNode {
    if left >= right {
        return lists[left]
    }
    mid := left + ((right - left) >> 1)
    l1 := merge(lists, left, mid)
    l2 := merge(lists, mid+1, right)
    return mergeTwoList(l1, l2)
}

func mergeTwoList(a, b *ListNode) *ListNode {
    p1, p2 := a, b
    dummy := &ListNode{Next: p1}
    cur := dummy
    for p1 != nil && p2 != nil {
        if p1.Val < p2.Val {
            cur.Next = p1
            cur = cur.Next
            p1 = p1.Next
        } else {
            cur.Next = p2
            cur = cur.Next
            p2 = p2.Next
        }
    }
    if p1 != nil {
        cur.Next = p1
    }
    if p2 != nil {
        cur.Next = p2
    }
    return dummy.Next
}
```

Last modification：July 9, 2025