【leetcode每日一题】23.Merge k Sorted Lists

悠悠 2022-08-04 14:42 146阅读 0赞

题目：Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

解析：可以先归并两个链表，然后依次归并所有链表。代码如下：

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1,ListNode* l2)
        {
            if(l1==NULL)
            {
                return l2;
            }
            if(l2==NULL)
            {
                return l1;
            }
            ListNode *result,*curNode;
            if(l1->val<l2->val)
            {
                result=curNode=l1;
                l1=l1->next;
            }
            else
            {
                result=curNode=l2;
                l2=l2->next;
            }
            while(l1!=NULL&&l2!=NULL)
            {
                if(l1->val<l2->val)
                {
                    curNode->next=l1;
                    l1=l1->next;
                }
                else
                {
                    curNode->next=l2;
                    l2=l2->next;
                }
                curNode=curNode->next;
            }
            if(l1!=NULL)
            {
                curNode->next=l1;
            }
            if(l2!=NULL)
            {
                curNode->next=l2;
            }
            return result;
        }
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if(lists.size()==0)
            {
                return NULL;
            }
            ListNode *result=lists[0];
            for(int i=1;i<lists.size();i++)
            {
                result=mergeTwoLists(result,lists[i]);
            }
            return result;
        }
    };