Merge k Sorted Lists（C++合并K个升序链表）

亦凉 2022-10-09 12:08 172阅读 0赞

(1) 两两合并

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
    public:
        ListNode* helper(ListNode *head1,ListNode *head2) {
            ListNode *n_head=new ListNode(0);
            ListNode *h_head=n_head;
            while(head1!=nullptr && head2!=nullptr) {
                if(head1->val<head2->val) {
                    ListNode *temp=head1->next;
                    h_head->next=head1;
                    head1=temp;
                } else if(head1->val>head2->val) {
                    ListNode *temp=head2->next;
                    h_head->next=head2;
                    head2=temp;
                } else {
                    ListNode *temp=head1->next;
                    ListNode *temp1=head2->next;
                    h_head->next=head1;
                    h_head=h_head->next;
                    h_head->next=head2;
                    head1=temp;
                    head2=temp1;
                }
                h_head=h_head->next;
            }
    
            if(head1!=nullptr) {
                h_head->next=head1;
            } else if(head2!=nullptr) {
                h_head->next=head2;
            } else h_head->next=nullptr;
            return n_head->next;
        }
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            ListNode *head=nullptr;
            for(int i=0;i<lists.size();i++) {
                head=helper(head,lists[i]);
            }
    
            return head;
        }
    };