Merging 2 linked lists and appending to the end of linked lists c++

Question

I don't have much so far but I am trying to get the hang of using linked lists.

Struct:

struct Node 
{
   int value;
   Node *next;
};

How can I add a node to the end of the list? I am just trying to take in a pointer for the head of a list and an int value to add in as a new node. When I try running what I have currently I get an exception.

void addNode(Node* head, int x) 
{

    Node* temp = new Node;
    temp->data = x;
    temp->next = NULL;

     if(!head) 
     { 
         head = temp;
         return;
     } 
     else 
     {
         Node* last = head;
         while(last->next) 
         last=last->next;

         last->next = temp;
     }
}

I haven't really begun to work on merging the two lists. I just know that I need to take in 2 linked lists (or pointers to the head of 2 linked lists?) and then run through the lists for all the nodes.

E.G: Linked list 1 has 3 nodes: 4, 10, 20. Linked List 2 has 4 nodes: 2, 5, 15, 60.

The merge list function would results in a new linked list with 2,4,5,10,15,20,60 as the nodes.

EDIT: In my main, I am calling the addNode function like so:

Node *head = new Node;

insertAtEnd(head,20);

Is that correct or could that be the cause of the exception?

Answer 1

Declare the function the following way

void addNode( Node* &head, int x) ;

And instead of this code snippet

Node *head = new Node;

insertAtEnd(head,20);

You have to call the function the first time the following way

Node *head = nullptr; // or NULL

addNode(head,20);

Notice that there is no function with name insertAtEnd in your post. There is function addNode.:)

If you need to merge two lists then you can use this demonstrative program as a sample. Of course you will need to add some other functions as for example deleting lists that to get a complete project.

#include <iostream>

struct Node 
{
    int value;
    Node *next;
};

Node * insert( Node *current, int value )
{
    Node *tmp;

    if ( current == nullptr )
    {
        tmp = new Node { value, nullptr };
    }
    else
    {
        tmp = new Node { value, current->next };
        current->next = tmp;
    }

    return tmp;
}

std::ostream & display( Node *head, 
                        std::ostream &os = std::cout,
                        const char *delimiter = " " )
{
    for ( ; head; head = head->next ) os << head->value << delimiter;

    return os;
}

Node * merge( Node * &head1, Node * &head2 )
{
    Node *new_head = nullptr;
    Node *current  = nullptr; 

    while ( head1 != nullptr && head2 != nullptr )
    {
        Node *tmp;
        if ( head2->value < head1->value )
        {
            tmp = head2;
            head2 = head2->next;
        }
        else
        {
            tmp = head1;
            head1 = head1->next;
        }

        tmp->next = nullptr;
        if ( new_head == nullptr )
        {
            new_head = tmp;
            current = new_head;
        }
        else
        {
            current->next = tmp;
            current = current->next;
        }
    }

    if ( head1 != nullptr ) new_head == nullptr ? new_head : current->next = head1;
    if ( head2 != nullptr ) new_head == nullptr ? new_head : current->next = head2;


    head2 = nullptr;
    head1 = new_head;

    return new_head;
}

int main() 
{
    Node *list1 = nullptr;
    Node *list2 = nullptr;

    list1 = insert( list1, 4 );
    insert( insert( list1, 10 ), 20 );

    display( list1, std::cout << "List1: " ) << std::endl;

    list2 = insert( list2, 2 );
    insert( insert( insert( list2, 5 ), 15 ), 60 );

    display( list2, std::cout << "List2: " ) << std::endl;

    std::cout << std::endl;

    merge( list1, list2 );

    display( list1, std::cout << "List1: " ) << std::endl;
    display( list2, std::cout << "List2: " ) << std::endl;

    return 0;
}

The program output is

List1: 4 10 20 
List2: 2 5 15 60 

List1: 2 4 5 10 15 20 60 
List2: 

Answer 2

By doing this:

void addNode(Node* head, int x) 
// here ---------^

and then later this:

 head = temp; // here

you're simply modifying the local head pointer, which took on the address value passed from the caller. Since head is not an actual reference to a pointer (it's just a pointer), the result is the caller's pointer passed as head remains unaltered. You never append your allocated node to your list, leak memory, it becomes a sad day...

Pass the pointer by reference instead. Fixing that, then fixing the invalid data member, which should actually be value and a pointer-to-pointer for walking the list to find the end, the result could look something like this:

#include <iostream>

struct Node
{
    int value;
    Node *next;
};

void addNode(Node*& head, int x)
{
    Node **pp = &head;
    while (*pp)
        pp = &(*pp)->next;
    *pp = new Node;
    (*pp)->value = x;
    (*pp)->next = nullptr;
}

void printList(const Node *head)
{
    for (; head; head = head->next)
        std::cout << head->value << ' ';
    std::cout << '\n';
}

void freeList(Node *&head)
{
    while (head)
    {
        Node *p = head;
        head = p->next;
        delete p;
    }
}

int main()
{
    Node *head = nullptr;

    for (int i=1; i<=5; ++i)
        addNode(head, i);

    printList(head);
    freeList(head);
}

Output

1 2 3 4 5 

I leave the task of implementing an actual merge to you, but this should be enough to get you a manageable list up and running.

---

Update: From the OP's edited question:

Node *head = new Node;

insertAtEnd(head,20);

Apart from now-being a completely different named function, your node is default-initialized. In your case that means the resulting Node from new Node; has indeterminate values for both value and next. You're then passing that to your function, which assumes a determinate value (null) to terminate your loop.

This can be fixed any number of ways; the mechanics of the code above is one such way. There is no need to pre-allocate a head node in the first place if the list management code is of the understanding that NULL means no-list. Your addNode original post seemed to at-least-try to follow that mantra.

Answer 3

EDIT: In my main, I am calling the addNode function like so:

Node *head = new Node;
insertAtEnd(head,20);

This is wrong. You didn't initialize head->next, so within insertAtEnd the code while(last->next) last=last->next; will attempt to compare uninitialized pointer and if it isn't null, will dereference it. This will likely crash your program rather than throw an exception though. Then again, it's undefined behaviour, so anything may happen.

Since your insert function already covers the case of inserting to empty list, I would simply call

head = nullptr;
insertAtEnd(head,20)`;

Besides that, there's the bug of never updating the head pointer outside the function, which has already been covered in other answers.

Answer 4

this may be a cause of exception:

struct Node 
{
   int value;     <-----  Node structure has value property
   Node *next;
};


Node* temp = new Node;
temp->data = x;   <------ Assigning to data property of Node which does not exists
temp->next = NULL;

To add list you may use same approach

void addNode(Node* head, Node* head2) 
{

  Node* last = head;
  while(last->next) last=last->next;

  last->next = head2;
}