LeetCode: 23. Merge k Sorted Lists

引言

引言

题目链接：https://leetcode.com/problems/merge-k-sorted-lists/description/

题目大意

合并k个已排序的链表并将其作为一个排序列表返回。分析并描述其复杂性。

Example

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Input:

[

1->4->5,

1->3->4,

2->6

]

Output: 1->1->2->3->4->4->5->6

题解

一句话题解：直接借用21题 Merge Two Sorted Lists 的双链表合并借用归并排序的思想分治合并即可

复杂度

时间复杂度 O(nlogn)

空间复杂度 O(1)

AC代码

c++版本

class Solution
{
  public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        int n = lists.size();
        if (0 == n)
        {
            return nullptr;
        }
        while (n > 1)
        {
            int mid = (n + 1) >> 1;
            for (int i = 0; i < (n >> 1); ++i)
            {
                lists[i] = mergeTwoLists(lists[i], lists[i + mid]);
            }
            n = mid;
        }
        return lists[0];
    }

  private:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        ListNode *pRet = new ListNode(0);
        ListNode *curNode = pRet;
        while (nullptr != l1 && nullptr != l2)
        {
            if (l1->val < l2->val)
            {
                curNode->next = l1;
                l1 = l1->next;
            }
            else
            {
                curNode->next = l2;
                l2 = l2->next;
            }
            curNode = curNode->next;
        }
        curNode->next = nullptr == l1 ? l2 : l1;
        return pRet->next;
    }
};

class Solution

{

public:

ListNode *mergeKLists(vector<ListNode *> &lists)

{

int n = lists.size();

if (0 == n)

{

return nullptr;

}

while (n > 1)

{

int mid = (n + 1) >> 1;

for (int i = 0; i < (n >> 1); ++i)

{

lists[i] = mergeTwoLists(lists[i], lists[i + mid]);

}

n = mid;

}

return lists[0];

}

private:

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)

{

ListNode *pRet = new ListNode(0);

ListNode *curNode = pRet;

while (nullptr != l1 && nullptr != l2)

{

if (l1->val < l2->val)

{

curNode->next = l1;

l1 = l1->next;

}

else

{

curNode->next = l2;

l2 = l2->next;

}

curNode = curNode->next;

}

curNode->next = nullptr == l1 ? l2 : l1;

return pRet->next;

}

};

go版本

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    pRet := &ListNode{0, nil}
    curNode := pRet
    for nil != l1 && nil != l2 {
        if l1.Val < l2.Val {
            curNode.Next = l1
            l1 = l1.Next
        } else {
            curNode.Next = l2
            l2 = l2.Next
        }
        curNode = curNode.Next
    }
    if nil != l1 {
        curNode.Next = l1
    } else {
        curNode.Next = l2
    }
    return pRet.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
    n := len(lists)
    if 0 == n {
        return nil
    }
    for n > 1 {
        mid := (n + 1) >> 1
        for i := 0; i < (n >> 1); i++ {
            lists[i] = mergeTwoLists(lists[i], lists[i+mid])
        }
        n = mid
    }
    return lists[0]
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {

pRet := &ListNode{0, nil}

curNode := pRet

for nil != l1 && nil != l2 {

if l1.Val < l2.Val {

curNode.Next = l1

l1 = l1.Next

} else {

curNode.Next = l2

l2 = l2.Next

}

curNode = curNode.Next

}

if nil != l1 {

curNode.Next = l1

} else {

curNode.Next = l2

}

return pRet.Next

}

func mergeKLists(lists []*ListNode) *ListNode {

n := len(lists)

if 0 == n {

return nil

}

for n > 1 {

mid := (n + 1) >> 1

for i := 0; i < (n >> 1); i++ {

lists[i] = mergeTwoLists(lists[i], lists[i+mid])

}

n = mid

}

return lists[0]

}

一	二	三	四	五	六	日
« 11月
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

LeetCode: 23. Merge k Sorted Lists

引言

题目大意

题解

复杂度

AC代码

发表评论取消回复

目前评论：2 其中：访客 1 博主 1