题解 | #合并k个已排序的链表#

合并k个已排序的链表

https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <vector>
class Solution {
public:

    ListNode * Merge2(ListNode * pHead1,ListNode * pHead2){
        if(pHead1 ==nullptr)
            return pHead2;
        if(pHead2 == nullptr)
            return pHead1;
        ListNode * head = new ListNode(0);
        ListNode * tail = head;

        while(pHead1 && pHead2){
            if(pHead1->val < pHead2->val){
                tail->next = pHead1;
                pHead1 = pHead1->next;
            }
            else{
                tail->next = pHead2;
                pHead2 = pHead2->next;
            }
            tail = tail->next;
        }
        if(pHead1){
            tail->next = pHead1;
        }
        else{
            tail->next = pHead2;
        }
        return head->next;
    }


    ListNode * divideMerge(vector<ListNode *> &lists,int left,int right){
        if(left > right)
            return nullptr;
        else if (left == right)
            return lists[left];
        int mid = (left + right) >> 1;
        return Merge2(divideMerge(lists, left, mid),divideMerge(lists, mid+1, right));
    }

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return divideMerge(lists,0,lists.size()-1);
    }
};

全部评论

相关推荐

Cherrycola01:0实习 0项目 约等于啥也没有啊 哥们儿这简历认真的吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务