Answer to Question #270712 in C++ for osama

Question

Write a function that will take two sorted singly linked List as input and merge them in third list. (You are not allowed to use any sorting algorithm) also give main for the function.

Answer 1

#include <cassert>

template<class T>
struct Node {
    T value;
    Node *next { nullptr };
};

template<class T>
Node<T>* Merge(Node<T> *lhs, Node<T> *rhs) {
    if (!lhs) return rhs;
    if (!rhs) return lhs;

    Node<T> * head = nullptr;
    if (lhs->value < rhs->value) {
        head = lhs;
        lhs = lhs->next;
    }
    else {
        head = rhs;
        rhs = rhs->next;
    }
    Node<T> * node = head;
    while (lhs || rhs) {
        if (lhs && rhs) {
            if (lhs->value < rhs->value) {
                node->next = lhs;
                node = lhs;
                lhs = lhs->next;
            }
            else {
                node->next = rhs;
                node = rhs;
                rhs = rhs->next;
            }
        }
        else {
            assert(lhs || rhs);
            node->next = lhs? lhs: rhs;
            break;
        }
    }
    return head;
}