Union of Two Linked Lists

Given two linked lists, your task is to complete the function makeUnion(), that returns the union of two linked lists. This union should include all the distinct elements only.

• Time : O(mlogm + nlogn)

• Space : O(1)

• merge sort solution

struct Node *mergeSort(struct Node *head) {
    if (!head->next) return head;
    Node *slow = head, *fast = head;
    while (fast and fast->next) {
        fast = fast->next;
        if (fast and fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    Node *mid = slow->next;
    slow->next = NULL;
    Node *left = mergeSort(head);
    Node *right = mergeSort(mid);

    Node *dummy = new Node(-1);
    Node *tail = dummy;
    while (left and right) {
        if (left->data < right->data) {
            tail->next = left;
            left = left->next;
        } else {
            tail->next = right;
            right = right->next;
        }
        tail = tail->next;
        tail->next = NULL;
    }
    if (left) tail->next = left;
    else tail->next = right;

    return dummy->next;
}

struct Node *makeUnion(struct Node *head1, struct Node *head2) {
    Node *sortedHead1 = mergeSort(head1);
    Node *sortedHead2 = mergeSort(head2);
    Node *dummy = new Node(-1);
    Node *tail = dummy;
    while (sortedHead1 and sortedHead2) {
        while(sortedHead1->next and sortedHead1->next->data == sortedHead1->data) sortedHead1 = sortedHead1->next;
        while(sortedHead2->next and sortedHead2->next->data == sortedHead2->data) sortedHead2 = sortedHead2->next;
        if (sortedHead1->data < sortedHead2->data) {
            tail->next = sortedHead1;
            sortedHead1 = sortedHead1->next;
        } else if (sortedHead1->data > sortedHead2->data) {
            tail->next = sortedHead2;
            sortedHead2 = sortedHead2->next;
        } else {
            tail->next = sortedHead1;
            sortedHead1 = sortedHead1->next;
            sortedHead2 = sortedHead2->next;
        }
        tail = tail->next;
        tail->next = NULL;
    }
    Node* remain;
    if(sortedHead1) remain = sortedHead1;
    else remain = sortedHead2;
    while(remain) {
        while(remain->next and remain->next->data == remain->data) remain = remain->next;
        tail->next = remain;
        remain = remain->next;
        tail = tail->next;
        tail->next = NULL;
    }

    return dummy->next;
}

• Time : O(klogk)

• Space : O(k)

• hash table solution

struct Node *mergeSort(struct Node *head) {
    if (!head->next) return head;
    Node *slow = head, *fast = head;
    while (fast and fast->next) {
        fast = fast->next;
        if (fast and fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    Node *mid = slow->next;
    slow->next = NULL;
    Node *left = mergeSort(head);
    Node *right = mergeSort(mid);

    Node *dummy = new Node(-1);
    Node *tail = dummy;
    while (left and right) {
        if (left->data < right->data) {
            tail->next = left;
            left = left->next;
        } else {
            tail->next = right;
            right = right->next;
        }
        tail = tail->next;
        tail->next = NULL;
    }
    if (left) tail->next = left;
    else tail->next = right;

    return dummy->next;
}

void insertWithoutDuplicates(unordered_set<int>& us, Node* node, Node** tail) {
    while(node) {
        if(!us.count(node->data)) {
            us.insert(node->data);
            (*tail)->next = node;
            (*tail) = (*tail)->next;
        }
        node = node->next;
        (*tail)->next = NULL;
    }
}

struct Node* makeUnion(struct Node* head1, struct Node* head2) {
    unordered_set<int> us;
    Node* dummy = new Node(-1);
    Node* tail = dummy;
    insertWithoutDuplicates(us, head1, &tail);
    insertWithoutDuplicates(us, head2, &tail);
    return mergeSort(dummy->next);
}