leetcode-23-Merge k Sorted Lists-合并K个排序链表

帘外五更风 · · 774 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

Merge k Sorted Lists

解题思路

链表两两合并，分而治之

代码-GoLang

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    p := list1
    q := list2
    var head, cur *ListNode
    var v int
    for p != nil || q != nil {
        if p == nil {
            v = q.Val
            q = q.Next
        } else if q == nil {
            v = p.Val
            p = p.Next
        } else {
            if q.Val < p. Val {
                v = q.Val
                q = q.Next
            } else {
                v = p.Val
                p = p.Next
            }
        }

        if head == nil {
            head = &ListNode{
                Val:v,
                Next:nil,
            }
            cur = head
        } else {
            cur.Next = &ListNode{
                Val:v,
                Next:nil,
            }
            cur = cur.Next
        }
    }
    return head
}

func merge(lists []*ListNode, st, en int) *ListNode {
    if st == en {
        return lists[st]
    }
    mid := st + (en - st + 1) / 2
    l1 := merge(lists, st, mid - 1)
    l2 := merge(lists, mid, en)
    return mergeTwoLists(l1, l2)
}

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

有疑问加站长微信联系（非本文作者）