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!