Combining 2 linked lists and adding to the end of C ++ linked lists
I don't have much yet, but I'm trying to use linked lists.
Struct:
struct Node
{
int value;
Node *next;
};
How do I add a node to the end of the list? I'm just trying to take a pointer to the title of the list and an int value to add as a new node. When I try to run what I have, 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 didn't really start working on combining the two lists. I just know that I need to take 2 linked lists (or head pointers from 2 linked lists?) And then run the lists for all nodes.
EG: Linked list 1 has 3 nodes: 4, 10, 20. Linked list 2 has 4 nodes: 2, 5, 15, 60.
The merge list function will result in a new linked list with 2,4,5,10,15,20,60 as nodes.
EDIT: Basically I am calling the addNode function like this:
Node *head = new Node;
insertAtEnd(head,20);
Is this correct or could it be the reason for the exception?
source to share
Declare the function like this
void addNode( Node* &head, int x) ;
And instead of this piece of code
Node *head = new Node;
insertAtEnd(head,20);
You must call the function the first time like this
Node *head = nullptr; // or NULL
addNode(head,20);
Please note that there is no named function in your post insertAtEnd
. There is a function addNode
. :)
If you need to combine two lists, you can use this demo program as a sample. Of course you will need to add some other functionality like deleting lists to get the 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;
}
Program output
List1: 4 10 20
List2: 2 5 15 60
List1: 2 4 5 10 15 20 60
List2:
source to share
By doing this:
void addNode(Node* head, int x)
// here ---------^
and then later:
head = temp; // here
you are just changing the local pointer head
which takes the address value passed from the caller. Since head
it is not an actual pointer reference (it is just a pointer), the result is the caller's pointer passed as head
remains unchanged. You never add your dedicated node to your list, memory leak, this becomes a sad day ...
Pass in a pointer instead of a link. Fixing this, then fixing the invalid element data
, which must be a value
pointer to a pointer to jump to the list to find the end, the result might 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'm leaving the task of implementing the actual merge to you, but it should be enough to get the managed list up and running.
Update: From the edited question:
Node *head = new Node;
insertAtEnd(head,20);
Also, if you use a completely different named function, your node is initialized by default. In your case, this means that the derived Node
from new Node;
has undefined values for value
and next
. Then you pass this to your function, which assumes a deterministic value (null) to complete the loop.
This can be fixed in any number of ways; the mechanics of the above code is one such way. It is not necessary to preallocate the head node in the first place if the list management code understands that NULL means "no list". Your original post addNode
at least tried to follow this mantra.
source to share
this could be the reason for the 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 a list you can use the same approach
void addNode(Node* head, Node* head2)
{
Node* last = head;
while(last->next) last=last->next;
last->next = head2;
}
source to share
EDIT: Basically I am calling the addNode function like this:
Node *head = new Node;
insertAtEnd(head,20);
It is not right. You have not initialized head->next
, so the insertAtEnd
code while(last->next) last=last->next;
will try to compare the uninitialized pointer, and if it is not null, it will dereference it. This will most likely cause your program to crash, not an exception. Again, this behavior is undefined, so something might happen.
Since your insert function already covers the case of inserting into an empty list, I would just call
head = nullptr; insertAtEnd(head,20)`;
Also, there is a bug in that the head
outside of the function pointer was never updated , which has already been covered in other answers.
source to share