Thread: Linked List "Changed by itself"

A background to the source code:

We build a linked list 1-2-3
We build a linked list 1-2-3-4-5

We use a function called ShuffleMerge that takes each node from both lists and alternates them. So mixing the above two lists gives:

1-1-2-2-3-3-4-5

See the code below:

Code:

# include <stdio.h>
# include <assert.h>
# include <stdlib.h>

struct node {
    int data;
    struct node* next;
};

void PrintLinkedList (struct node* head) {
    if (head == NULL) {
        printf("Null List");
        return;
        }
    while (head -> next != NULL) {
        printf("%d ", head -> data);
        head = head -> next;
        }
    printf("%d", head -> data);
    return;
}

struct node* BuildOneTwoThree() {
    struct node* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;
    head = malloc (sizeof(struct node));
    second = malloc (sizeof(struct node));
    third = malloc (sizeof(struct node));
    head -> data = 1;
    head -> next = second;
    second -> data = 2;
    second -> next = third;
    third -> data = 3;
    third -> next = NULL;
    return (head);
}

struct node* BuildOneTwoThreeFourFive() {
    struct node* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;
    struct node* fourth = NULL;
    struct node* fifth = NULL;
    head = malloc (sizeof(struct node));
    second = malloc (sizeof(struct node));
    third = malloc (sizeof(struct node));
    fourth = malloc (sizeof(struct node));
    fifth = malloc (sizeof(struct node));
    head -> data = 1;
    head -> next = second;
    second -> data = 2;
    second -> next = third;
    third -> data = 3;
    third -> next = fourth;
    fourth -> data = 4;
    fourth -> next = fifth;
    fifth -> data = 5;
    fifth -> next = NULL;
    return (head);
}

void MoveNode (struct node** destRef, struct node** sourceRef) {
    if (*sourceRef == NULL)
        return;
    struct node* temp = *destRef;
    *destRef = *sourceRef;
    *sourceRef = (*sourceRef) -> next;
    (*destRef) -> next = temp;
}

struct node* ShuffleMerge(struct node* a, struct node* b) {
    struct node dummy;
    struct node* tail = &dummy;
    dummy.next = NULL;
    while (!(a == NULL && b == NULL)) {
        if (a != NULL) {
            MoveNode (&(tail -> next), &a);
            tail = tail -> next;
        }
        if (b != NULL) {
            MoveNode (&(tail -> next), &b);
            tail = tail -> next;
        }
    }
    //PrintLinkedList (a);      Just before its returned, a points to a NULL List, confirmed by printing it at this line
    return (dummy.next);
}

int main() {
    struct node* a = BuildOneTwoThree();
    struct node* b = BuildOneTwoThreeFourFive();
    PrintLinkedList (ShuffleMerge(a, b)); // Here the returned head pointer from the shuffle merge function is printed
    printf("\n");
    PrintLinkedList (a); // Heres the problem, when "a" exited the ShuffleMerge function, it was NULL as it should be. But when its printed here, it points to the shuffled linked list!
    getchar();
}

I got the programme to work no problem. But just as a matter of interest theres one anomoly which I cant explain and its the second last statement:
"a" points to the returned shuffled list and not to NULL as it should!

I think itll take too long a time to get the actual code. The point I dont get focuses on TWO statements:
Line 86 where we print a and it prints NULL
Line 95 where the code imediately jumps to after line 86 and it all of a sudden prints 1-1-2-2-3-3-4-5 !
And thats anomolous because just as it exited the shuffle merge function it was NULL and no operation whatsoever was performed on it. It obviously has something to do with the fact that a COPY of the pointer was passed to sufflemerge and not a pointer to the pointer, but I still cant make out what exactly. Answer is staring me in the face!

a in ShuffleMerge and a in main are two different variables.
a in Shuffelmerge is NULL a in main should have the value returned by BuildOneTwoThree.

Originally Posted by sparkomemphis

a in ShuffleMerge and a in main are two different variables.
a in Shuffelmerge is NULL a in main should have the value returned by BuildOneTwoThree.

Thats exactly what its doing but why? Shouldnt it stay NULL?