I am trying to understand merging two sorted lists into one sorted output. Got the below code from internet. trav's value will have to be the address of mergedHead but here, trav is holding the value of mergedHead and *mergedHead have a value equivalent to *trav's value. Could anyone please let me know why this is happening?
This page is not helpful.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
}Node;
Node *createNode(int data) {
Node *newNode = (Node *) malloc(sizeof(Node));
if(!newNode) {
printf("mem-alloc failed for data: %d\n", data);
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
Node *mergeTwoSortedLists(Node *head1, Node *head2) {
Node *mergedList = NULL;
Node **trav = &mergedList;
if(!head1 && !head2) {
printf("Both the heads are NULL, cant merge\n");
return NULL;
}
while (head1 && head2) {
if(head1->data <= head2->data) {
*trav = createNode(head1->data);
printf("&trav: %p trav: %p, *trav: %p, **trav: %d, &mergedList: %p, mergedList: %p, *mergedList: %p\n", &trav, trav, *trav, **trav, &mergedList, mergedList, *mergedList);
head1 = head1->next;
}
else {
*trav = createNode(head2->data);
printf("&trav: %p trav: %p, *trav: %p, **trav: %d, &mergedList: %p, mergedList: %p, *mergedList: %p\n", &trav, trav, *trav, **trav, &mergedList, mergedList, *mergedList);
head2 = head2->next;
}
trav = &((*trav)->next);
}
/* insertion of the remaining list to the trav
or insert the list that is not null. */
while (head1) {
*trav = createNode(head1->data);
printf("&trav: %p trav: %p, *trav: %p, **trav: %d, &mergedList: %p, mergedList: %p, *mergedList: %p\n", &trav, trav, *trav, **trav, &mergedList, mergedList, *mergedList);
head1 = head1->next;
trav = &((*trav)->next);
}
while (head2) {
*trav = createNode(head2->data);
printf("&trav: %p trav: %p, *trav: %p, **trav: %d, &mergedList: %p, mergedList: %p, *mergedList: %p\n", &trav, trav, *trav, **trav, &mergedList, mergedList, *mergedList);
head2 = head2->next;
trav = &((*trav)->next);
}
return mergedList;
}
void createSortedList(Node **head, int data) {
Node *trav = NULL;
Node *newNode = (Node *) malloc(sizeof(Node));
if(!newNode) {
printf("Memalloc failed - No memory allocated for data: %d\n", data);
return;
}
newNode->data = data;
if(!(*head) || (*head)->data >= data) {
newNode->next = *head;
*head = newNode;
return;
}
trav = *head;
while((trav->next) && (trav->next->data < data)) {
trav = trav->next;
}
newNode->next = trav->next;
trav->next = newNode;
return;
}
void printList(Node *head) {
if(!head) {
printf("Node is empty\n");
return;
}
while(head) {
printf("%d\t", head->data);
head = head->next;
}
printf("\n");
return;
}
int main() {
Node *head = NULL;
Node *head2 = NULL;
Node *head3 = NULL;
createSortedList(&head, 3);
createSortedList(&head, 5);
createSortedList(&head, 7);
createSortedList(&head, 3);
createSortedList(&head, 4);
createSortedList(&head, 9);
printList(head);
createSortedList(&head2, 10);
createSortedList(&head2, 5);
createSortedList(&head2, 9);
createSortedList(&head2, 4);
printList(head2);
head3 = mergeTwoSortedLists(head, head2);
printList(head3);
return 0;
}
Output:
PS C:\Users\42410\Desktop\C\VSCode\LinkedList> .\a.exe
3 3 4 5 7 9
4 5 9 10
&trav: 0061FED8 trav: 0061FEDC, *trav: 007C0E28, **trav: 3, &mergedList: 00000000, mergedList: 0061FEDC, *mergedList: 007C0E28
&trav: 0061FED8 trav: 007C0E2C, *trav: 007C0E38, **trav: 3, &mergedList: 00000000, mergedList: 0061FEDC, *mergedList: 007C0E28
&trav: 0061FED8 trav: 007C0E3C, *trav: 007C0E48, **trav: 4, &mergedList: 00000000, mergedList: 0061FEDC, *mergedList: 007C0E28
&trav: 0061FED8 trav: 007C0E4C, *trav: 007C0E58, **trav: 4, &mergedList: 00000000, mergedList: 0061FEDC, *mergedList: 007C0E28
&trav: 0061FED8 trav: 007C0E5C, *trav: 007C0E68, **trav: 5, &mergedList: 00000000, mergedList: 0061FEDC, *mergedList: 007C0E28
&trav: 0061FED8 trav: 007C0E6C, *trav: 007C0E78, **trav: 5, &mergedList: 00000000, mergedList: 0061FEDC, *mergedList: 007C0E28
&trav: 0061FED8 trav: 007C0E7C, *trav: 007C0E88, **trav: 7, &mergedList: 00000000, mergedList: 0061FEDC, *mergedList: 007C0E28
&trav: 0061FED8 trav: 007C0E8C, *trav: 007C04B0, **trav: 9, &mergedList: 00000000, mergedList: 0061FEDC, *mergedList: 007C0E28
&trav: 0061FED8 trav: 007C04B4, *trav: 007C0F20, **trav: 9, &mergedList: 00000000, mergedList: 0061FEDC, *mergedList: 007C0E28
&trav: 0061FED8 trav: 007C0F24, *trav: 007C0EE0, **trav: 10, &mergedList: 00000000, mergedList: 0061FEDC, *mergedList: 007C0E28
3 3 4 4 5 5 7 9 9 10
PS C:\Users\42410\Desktop\C\VSCode\LinkedList>
Your print statement is wrong.
If you didn't get any warnings from the compiler, it's time to increase warning level. For instance for gcc use the options: -Wall -Wextra -Werror -pedantic
When printing a pointer (i.e. %p) you need to cast the pointer to void-pointer. Like:
int x;
int* p = &x;
printf("p equals %p\n", (void*)p);
^^^^^^^
cast to void*
Worse is that **trav is of type Node but you print it using %d. You probalbly wanted to print (**trav).data.
And kind of the same for *mergedList. Again it's a Node but this time you print it using %p. Maybe you wanted %d together with (*mergedList).data.
All this means that your program has undefined behavior. Notice for instance the print &mergedList: 00000000. That's all wrong. The address of a local variable can't be 00000000.
Instead try:
printf("&trav: %p trav: %p, *trav: %p, **trav: %d, &mergedList: %p, mergedList: %p, *mergedList: %d\n", (void*)&trav, (void*)trav, (void*)*trav, (**trav).data, (void*)&mergedList, (void*)mergedList, (*mergedList).data);
That said, I would recommend that you avoid such a long printf statement. Break it into a number of simpler statements. Like:
printf("&trav: %p, ", (void*)&trav);
printf("trav: %p, ", (void*)trav);
printf("*trav: %p, ", (void*)*trav);
printf("(**trav).data: %d, ", (**trav).data);
printf("&mergedList: %p, ", (void*)&mergedList);
printf("mergedList: %p, ", (void*)mergedList);
printf("(*mergedList).data: %d\n", (*mergedList).data);
Much easier to read. Much easier to make sure things are correct.
Since you do the same print 4 times, you could consider using a macro to avoid typing the same several times.
#define DUMP_VALUES \
printf("&trav: %p, ", (void*)&trav); \
printf("trav: %p, ", (void*)trav); \
printf("*trav: %p, ", (void*)*trav); \
printf("(**trav).data: %d, ", (**trav).data); \
printf("&mergedList: %p, ", (void*)&mergedList); \
printf("mergedList: %p, ", (void*)mergedList); \
printf("(*mergedList).data: %d\n", (*mergedList).data)
Then to do the print just write:
DUMP_VALUES;
After these changes, my system prints:
3 3 4 5 7 9
4 5 9 10
&trav: 0x7ffea69fcb20, trav: 0x7ffea69fcb28, *trav: 0x2134160, (**trav).data: 3, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134168, *trav: 0x2134180, (**trav).data: 3, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134188, *trav: 0x21341a0, (**trav).data: 4, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x21341a8, *trav: 0x21341c0, (**trav).data: 4, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x21341c8, *trav: 0x21341e0, (**trav).data: 5, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x21341e8, *trav: 0x2134200, (**trav).data: 5, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134208, *trav: 0x2134220, (**trav).data: 7, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134228, *trav: 0x2134240, (**trav).data: 9, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134248, *trav: 0x2134260, (**trav).data: 9, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
&trav: 0x7ffea69fcb20, trav: 0x2134268, *trav: 0x2134280, (**trav).data: 10, &mergedList: 0x7ffea69fcb28, mergedList: 0x2134160, (*mergedList).data: 3
3 3 4 4 5 5 7 9 9 10
which makes much more sense than OPs result.