mergeTwoLists.cpp

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

// 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) {
        return merge(l1, l2, NULL, NULL);
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2,  ListNode* head, ListNode* iterator) {
        
        if (l1 == NULL && l2 == NULL) {
            return head;
        }

        if (head == NULL) {
            if (l1 == NULL) {
                head = new ListNode(l2->val);
                iterator = head;
                return merge(l1, l2->next, head, iterator);
            } else if (l2 == NULL) {
                head = new ListNode(l1->val);
                iterator = head;
                return merge(l1->next, l2, head, iterator);
            } else if (l1->val < l2->val) {
                head = new ListNode(l1->val);
                iterator = head;
                return merge(l1->next, l2, head, iterator);
            } else {
                head = new ListNode(l2->val);
                iterator = head;
                return merge(l1, l2->next, head, iterator);
            }
        } else {
            if (l1 == NULL) {
                iterator->next = new ListNode(l2->val);
                return merge(l1, l2->next, head, iterator->next);
            } else if (l2 == NULL) {
                iterator->next = new ListNode(l1->val);
                return merge(l1->next, l2, head, iterator->next);
            } else if (l1->val < l2->val) {
                iterator->next = new ListNode(l1->val);
                return merge(l1->next, l2, head, iterator->next);
            } else {
                iterator->next = new ListNode(l2->val);
                return merge(l1, l2->next, head, iterator->next);
            }
        }
    }
};

int main(int argc, char**argv) {

    auto p1 = ListNode(2);
    auto p2 = ListNode(2);
    auto p3 = ListNode(4);

    auto p4 = ListNode(1);
    auto p5 = ListNode(3);
    auto p6 = ListNode(4);

    // p1.next = &p2;
    // p2.next = &p3;

    p4.next = &p5;
    p5.next = &p6;

    auto obj = Solution();
    // auto p = obj.mergeTwoLists(&p1, &p4);
    auto p = obj.mergeTwoLists(NULL, new ListNode(0));

    while(1) {
        cout << p->val << endl;
        p = p->next;
        if (p == NULL) {
            break;
        }
    }

    return 0;
}