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>
Node *newNode = malloc(sizeof *newNode);. No cast is required in C, so don't use one unless you plan to port the code to C++, and basing the size calculation on the identifier is less error-prone; if we change the type ofnewNode, it automatically follows.