合并K个排序链表

题目描述

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
            }

        }

    }
}

思路

因为是顺序链表，索引使用顺序合并。看题解还有分支的解，这个还要再好好思考！