合并K个排序链表
2020-04-26 本文已影响0人
7赢月
题目描述
https://leetcode-cn.com/problems/merge-k-sorted-lists/
解
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
if len(lists) == 1 {
return lists[0]
}
var head *ListNode
var next = head
for {
// 三个指针 遍历
// 比较三个指针 小的向后移动
var (
sIndex int
s = math.MaxInt32
c int
t ListNode
n int
)
for k, v := range lists {
if v == nil {
c++
continue
}
if s > v.Val {
s = v.Val
sIndex = k
}
}
// 终止条件
if c == len(lists) {
return head
}
if sIndex < len(lists) {
// 链接
n++
t.Val = lists[sIndex].Val
var now = lists[sIndex]
lists[sIndex] = lists[sIndex].Next
now.Next = nil
// 创建新节点
if next == nil {
if n == 1 {
head = now
}
next = now
} else {
next.Next = now
next = next.Next
}
}
}
}
思路
因为是顺序链表,索引使用顺序合并。看题解还有分支的解,这个还要再好好思考!