【虾皮面试手撕算法】：合并两个有序链表

本文主要是介绍【虾皮面试手撕算法】：合并两个有序链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int val_) : val(val_), next(nullptr){}
};

ListNode* Merge(ListNode* l1, ListNode* l2){
    ListNode* dummy = new ListNode(-1);
    ListNode* curr = dummy;
    while(l1 && l2){
        if(l1->val < l2->val){
            curr->next = l1;
            l1 = l1->next;
        }
        else{
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    curr->next = l1 == nullptr ? l2 : l1;
    curr = dummy->next;
    delete dummy;
    dummy = nullptr;
    return curr;
}

int main(){
    string str;
    getline(cin, str);
    int l1_left_pos = str.find('[', 0) + 1;
    int l1_right_pos = str.find(']', l1_left_pos);
    int l2_left_pos = str.find('[', l1_right_pos) + 1;
    int l2_right_pos = str.find(']', l2_left_pos);
    stringstream ss1(str.substr(l1_left_pos, l1_right_pos - l1_left_pos));
    stringstream ss2(str.substr(l2_left_pos, l2_right_pos - l2_left_pos));
    ListNode* dummy1 = new ListNode(-1);
    ListNode* dummy2 = new ListNode(-1);
    ListNode* curr1 = dummy1;
    ListNode* curr2 = dummy2;
    string temp;
    while(getline(ss1, temp, ',')){
        curr1->next = new ListNode(stoi(temp));
        curr1 = curr1->next;
    }
    while(getline(ss2, temp, ',')){
        curr2->next = new ListNode(stoi(temp));
        curr2 = curr2->next;
    }
    curr1 = dummy1->next;
    curr2 = dummy2->next;
    delete dummy1;
    dummy1 = nullptr;
    delete dummy2;
    dummy2 = nullptr;
    ListNode* head = Merge(curr1, curr2);
    cout << "[";
    while(head->next){
        cout << head->val << ",";
        head = head->next;
    }
    cout << head->val << "]";
    return 0;
}

这篇关于【虾皮面试手撕算法】：合并两个有序链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！