Merge two LinkedList without creating a new LinkedList

Question

I am trying to take the two linkedlist that I have in my executable file and merge them into each other in alternating positions. Ex. ListOne 1,2,3 and ListTwo 4,5 the new ListOne should be 1,4,2,5,3.

LinkedList .h file:

class LinkedList
{
private:
struct ListNode
{
    string firstName;
    string lastName;
    long int phoneNumber;
    struct ListNode *next;
};
ListNode *head;

public:
LinkedList()
{
    head = nullptr;
}
~LinkedList();
void appendNode(string f, string l, long int p);
void displayList();
};

LinkedList .cpp file:

LinkedList::~LinkedList()
{
cout << "LinkList destructor" << endl;
}

void LinkedList::appendNode(string f, string l, long int p)
{
    ListNode *newNode;
    ListNode *nodePtr;
    newNode = new ListNode;

    newNode -> firstName = f;
    newNode -> lastName = l;
    newNode -> phoneNumber = p;
    newNode -> next = nullptr;

    if (!head)
        head = newNode;

    else
    {
        nodePtr = head;

        while (nodePtr -> next)
            //while nodePtr is pointing to another node
            nodePtr = nodePtr -> next;
            //move to that node

        nodePtr -> next = newNode;
        //inset the newNode at the end of the linked list
    }
 }

 void LinkedList::displayList()
{
    ListNode *nodePtr;
    nodePtr = head;

    while(nodePtr)
    //while nodePtr is true, meaning there is a node in the list
    {
        cout << nodePtr -> firstName << endl;
        cout << nodePtr -> lastName << endl;
        cout << nodePtr -> phoneNumber << endl;
        nodePtr = nodePtr -> next;
     }
}

Executable file:

LinkedList ListOne;
LinkedList ListTwo;

ListOne.appendNode("Cate", "Beckem", 7704563454);
ListOne.appendNode("Cabe","Tomas", 7703451523);

ListTwo.appendNode("Mary", "Smith", 4043456543);
ListTwo.appendNode("Mark", "Carter", 4045433454);

My programs runs perfectly including the displayList function. I am just very confused how to go about making a merge function.

Answer 1

Making a merge function is not difficult. You can just use a new head to record the new list, then traverse these two lists and move the node from these two lists to new list in turn, like the following.

 LinkedList LinkedList::merge(LinkedList b)
{
    // if one list is null, return the other
    if (this->head == nullptr)
        return b;
    if (b.head == nullptr)
        return *this;

    LinkedList newlist;
    ListNode *ap = this->head, *bp = b.head, *p = nullptr;
    // if two pointer is all not null, move node from these to new list in turn
    while (ap != nullptr && bp != nullptr)
    {
        if (newlist.head == nullptr)
        {
            p = newlist.head = ap;
            ap = ap->next;
            p = p->next = bp;
            bp = bp->next;
        }
        else
        {
            p = p->next = ap;
            ap = ap->next;
            p = p->next = bp;
            bp = bp->next;
        }
    }
    // maybe one list is longer, and there is some node left.
    if (ap != nullptr)
        p->next = ap;
    if (bp != nullptr)
        p->next = bp;
    //clear original list
    this->head = b.head = nullptr;
    //if you want to merge list b to the caller list, you can change to
    //this->head = newlist->head and beginning part also need some modification.
    return newlist;
}

Maybe you don't want to change the original list, then you can just copy the value and create new node for the new list.

Answer 2

That merging is inserting nodes, which have been copied from or will be stolen from the source list, into the target list at certain positions.

I assume you want to treat the source list as immutable on that op, so the source nodes will be copied.

What is useful for both the copy and insert operation is an iterator - something that points to a node and, after a ++-op points to the next node in the list or behind the list end (to the equivalent of a nullptr):

(I write such snippets in a single source file; move the implementations to the .cpp files or inline them)

//
#include <type_traits>
using std::conditional;
#include <stdexcept>
using std::runtime_error;

class LinkedList
{


private:
    // [...]

    template <bool const_tag>
    struct NodeIterator {
        using element_type = typename conditional<
            const_tag,
            const ListNode,
            ListNode
        >::type;
        using pointer_type = element_type*;
        using reference_type = element_type&;

        static const NodeIterator end;

        NodeIterator(pointer_type p_in = nullptr) : p(p_in) {}

        NodeIterator& operator++ () {
            if (nullptr == p)
                throw runtime_error("Attempt to dereference nullptr");
            this->p = p->next;
            return *this;
        }

        bool operator== (const NodeIterator& rhs) const {
            return this->p != rhs.p;
        }

        bool operator!= (const NodeIterator& rhs) const {
            return !(*this == rhs);
        }

        pointer_type operator->() const {
            return p;
        }

        reference_type operator*() const {
            if (nullptr == p)
                throw runtime_error("Attempt to dereference nullptr");
            return *p;
        }

    private:
        pointer_type p;    
    }; // template <bool const_tag> struct NodeIterator

    static constexpr bool mutable_tag = false; 
    static constexpr bool const_tag = true; 

    using iterator_type = NodeIterator<mutable_tag>;
    using const_iterator_type = NodeIterator<const_tag>;


public:     
    LinkedList() :  head(nullptr) {}

    iterator_type begin() const { return iterator_type(head); }
    const iterator_type& end() const { return iterator_type::end; }

    const_iterator_type cbegin() const { return const_iterator_type(head); }
    const const_iterator_type& cend() const { return const_iterator_type::end; }
    // [...]    


}; // class LinkedList


// [...]    
template<bool is_const>
const LinkedList::NodeIterator<is_const>
LinkedList::NodeIterator<is_const>::end(nullptr);

// [...]

Now in the merge function code you position your iterators at the head of the respective lists

auto it_one = listOne.begin();
auto it_two = listTwo.cbegin();

and incremement it_one until it points to the element of the target list after which the copy is to be inserted, and incremement it_two until it points to the node of the source list to be copied, then

ListNode& one = *it_one;
ListNode* ptwo = new ListNode(*it_two); // copies

ptwo->next = one.next;
one.next = ptwo;

And that's it essentially.

Thus, the real issue here is not the how-to merge technically, but the complexity of the operations.

As long as both list are sorted in the intended order of the result list to be created, you can re-use the iterators, and thus plainly traverse both lists and it's O(N) with N = max(size(listOne), size(listTwo)).

If you have to sort them preliminarily to keep the merge itself cheap, that sorting causes O(N log N) complexity.

---

As a side note, having that iterators in store also simplifies implementing the other ops; e.g. displaying them is just

for (const auto& node : ListOne) {
    std::cout << node.firstName << std::endl;
    std::cout << node.lastName << std::endl;
    std::cout << node.phoneNumber << std::endl;
}