Merge Linked Lists

• Time : O(n+m)
• Space : O(1)

#include <vector>

using namespace std;

// This is an input class. Do not edit.
class LinkedList {
public:
    int value;
    LinkedList *next;

    LinkedList(int value) {
        this->value = value;
        next = nullptr;
    }
};

LinkedList *mergeLinkedLists(LinkedList *headOne, LinkedList *headTwo) {
    LinkedList* dummy = new LinkedList(-1);
    LinkedList* tail = dummy;
    while(headOne and headTwo) {
        if(headOne->value < headTwo->value) {
            tail->next = headOne;
            headOne = headOne->next;
        } else {
            tail->next = headTwo;
            headTwo = headTwo->next;
        }
        tail = tail->next;
    }
    if(headOne) tail->next = headOne;
    if(headTwo) tail->next = headTwo;
    return dummy->next;
}