malloc - How a pointer to pointer pointing to a NULL pointer works in C?

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>

#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>

Share Improve this question edited Nov 16, 2024 at 11:58 asked Nov 16, 2024 at 6:26 Preethi 551 silver badge10 bronze badges

@4386427, Hi, Yes, it is mergedList. – Preethi Commented Nov 16, 2024 at 8:14
Is it intentional, that your merge function makes a copy of both lists and doesn't just move the existing nodes into the merged list? – Gerhardh Commented Nov 16, 2024 at 12:09
Prefer: 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 of newNode, it automatically follows. – Kaz Commented Nov 16, 2024 at 13:19

Add a comment |

1 Answer 1

Sorted by: Reset to default 0

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.

科技改变生活-雨落星辰 - 所有的伟大,都源于一个勇敢的开始

malloc - How a pointer to pointer pointing to a NULL pointer works in C? - Stack Overflow

1 Answer 1

与本文相关的文章

评论列表(0)