算法面试通关40讲

三分学 七分练

数组、链表

leetcode 21

site

#include <iostream>
using namespace std;
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 *mergeTwoLists(ListNode *list1, ListNode *list2) {
        if (list1 == nullptr || list2 == nullptr) {
            return list1 == nullptr ? list2 : list1;
        }
        // tail insert
        ListNode header;
        ListNode *tail = &header;
        ListNode *tmp;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val > list2->val) {
                tmp = list1;
                list1 = list2;
                list2 = tmp;
            }
            tail->next = list1;
            while (list1 != nullptr && list1->val <= list2->val) {
                tmp = list1;
                list1 = list1->next;
            }
            tail = tmp;
        }
        if (list1 == nullptr) {
            tmp->next = list2;
        }
        return header.next;
    }
};
int main() {
    ListNode list1_4(4);
    ListNode list1_2(2, &list1_4);
    ListNode list1_1(1, &list1_2);
    ListNode list2_4(4);
    ListNode list2_3(3, &list2_4);
    ListNode list2_1(1, &list2_3);
    Solution sol;
    ListNode *result = sol.mergeTwoLists(&list1_1, &list2_1);
}