As this is a very common task for beginners I will left below some arguments and a complete C code example and expected output. I think it may help others.
Using your functions these code loops forever:
concatenation(second, first);
Display(third);
printf("\n");
concatenation(second, first);
Display(third);
printf("\n");
So you can see concatenation() is not working.
This also loops:
mergeLL(first, second);
Display(fourth);
printf("\n");
mergeLL(first, second);
Display(fourth);
printf("\n");
- So
mergeLL() is also problematic.
As you were told by Eric and others global values are problematic, much more if they points to allocated stuff.
- As you write code that
malloc things also you must write code to free these things. This is basic for a good life with C
A node is not a (linked) list
This is the linked list as in your code:
struct Node
{
int data;
struct Node* next;
}
But this is just a node. It is even named Node.
- A node is not a list. A list is not a node.
- A linked list is a --- possibly empty --- set of nodes.
- The nodes points to or contains data. In your case the data is a single
int value.
- A list is a collection of nodes ---
java naming --- or a container of nodes --- C++ naming.
- Your code does not even have a
struct list. But it should have. As close as your model is to the data the easier your code becomes.
create1 and create2 are not the same. But ARE
In your code they differ by the list address, first or second, both global values.
Good for you that there are only 2 lists and not 200, or you will end up with a very strange piece of code. Here you see the reason of pointer and arguments exists...
a safer approach
I will let here an example
a list
typedef struct st_node
{
int data;
struct st_node* next;
} Node;
typedef struct
{
unsigned size;
Node* head;
Node* tail;
} List;
So we now have List and it is a list of nodes Node. And both are names created by typedef. And List has metadata: keeping size updated makes total sense, as you will see in the example.
creating lists vc inserting data
List* create();
List* destroy();
int insert(int data, List* list);
int display(List* list, const char* title);
Here we have code to create and destroy List. insert() is a separate function, since insertion it is not part of the creation of a list.
And display() has an optional title, very convenient in the testing phase...
And create and destroy does just the expected.
destroy() returns NULL and it is very handy in order to invalidate the list pointer at the same time the list is destroyed: no invalid pointer is possible if you write
List* my_list = create();
// ...
my_list = destroy(my_list);
merge() and concat() returns new lists
List* concat(List* one, List* other);
List* merge(List* one, List* other);
concat and merge returns new lists. This is the safe way to go: no globals, all data is copied.
The list in this example
typedef struct st_node
{
int data;
struct st_node* next;
} Node;
typedef struct
{
unsigned size;
Node* head;
Node* tail;
} List;
List* create();
List* destroy(List* toGo);
List* concat(List* one, List* other);
int display(List* list, const char* title);
int insert(int data, List* list);
int insert_sorted(int data, List* list);
List* merge(List* one, List* other);
new here is
int insert_sorted(int data, List* list);
that just inserts data in the sorted (ascending) position. It is the simplest way to merge lists.
This declarations are the code that usually goes to a header file and gives a view of what you are implementing. If you write this as xlist.h and the code in xlist.c then you can write as many versions of test code or main.c as you need, whithout even recompling xlist.c. Nothing new, but convenient.
Note that there are no globals and no functions returning void. Functions return 0 for success or error codes. Or pointers to data.
simple versions of create, destroy and display
List* create()
{
List* one = malloc(sizeof(List));
if (one == NULL) return NULL;
one->size = 0;
one->head = NULL;
one->tail = NULL;
return one;
};
List* destroy(List* gone)
{
if (gone == NULL) return NULL;
for (unsigned i = 0; i < gone->size; i += 1)
{
Node* p = gone->head->next;
free(gone->head);
gone->head = p;
}
free(gone);
return NULL;
};
int display(List* list, const char* title)
{
if (title != NULL) printf("%s", title);
if (list == NULL)
{
printf("\nList does not exist\n");
return 0;
}
printf("\nList size: %u\n [ ", list->size);
Node* p = list->head;
for (unsigned i = 0; i < list->size; i += 1)
{
printf("%d ", p->data);
p = p->next;
}
printf("]\n\n");
return 0;
};
Since we have size it is easy to free all memory allocated for Node and List items.
Note that a program like
int main(void)
{
List* one = create();
display(one, "testing: Empty LIST");
one = destroy(one);
display(one, "testing: No list");
one = destroy(one);
return 0;
}
Can already run and it should print
testing: Empty LIST
List size: 0
[ ]
testing: No list
List does not exist
But it works already freeing all memory allocated.
versions of insert() and insert_sorted
int insert(int data, List* list)
{ // insert at last element
if (list == NULL) return -1;
Node* p = malloc(sizeof(Node));
p->data = data; // data copied to node
p->next = NULL; // inserted at tail
if (list->size == 0)
{
list->head = list->tail = p;
list->size = 1;
return 0;
}
list->tail->next = p;
list->tail = p;
list->size += 1; // count it in
return 0;
}
int insert_sorted(int data, List* list)
{
// insert in position according to value
if (list == NULL) return -1;
Node* p = malloc(sizeof(Node));
p->data = data; // data copied to node
p->next = NULL; // inserted at tail
if (list->size == 0)
{
list->head = list->tail = p;
list->size = 1;
return 0;
}
Node* pos = list->head;
Node* prev = NULL;
while (pos->data < data)
{
if (pos == list->tail)
{ // new element is the greatest
pos->next = p;
list->tail = p;
list->size += 1;
return 0;
}
prev = pos;
pos = pos->next; // advance
}; // end while()
// 'pos' is the insertion point
if (pos == list->head)
{ // new head
list->head = p;
p->next = pos;
list->size += 1;
return 0;
}
// insert before 'pos'
prev->next = p;
p->next = pos;
list->size += 1; // count it in
return 0;
}
To insert in ascending order of data takes no more than 25 lines. Code would be simpler if we had also pointer to previous node in Node struct: single linked lists are more complicated and not the reverse...
the original example using this mode
int main(void)
{
List* one = build_list(
10, (int[]){3, 4, 5, 7, 10, 15, 20, 25, 25, 30});
display(one, "'one'");
List* other = build_list(3, (int[]){2, 8, 9});
display(other, "'other'");
List* both = merge(one, other);
display(both, "merge(one,other)");
both = destroy(both);
both = concat(one, other);
display(both, "concat(one,other)");
one = destroy(one);
other = destroy(other);
both = destroy(both);
return 0;
}
output of this example
'one'
List size: 10
[ 3 4 5 7 10 15 20 25 25 30 ]
'other'
List size: 3
[ 2 8 9 ]
merge(one,other)
List size: 13
[ 2 3 4 5 7 8 9 10 15 20 25 25 30 ]
concat(one,other)
List size: 13
[ 3 4 5 7 10 15 20 25 25 30 2 8 9 ]
build_list helper function
List* build_list(unsigned N, const int data[])
{
List* L = create(); // new list
if ((N == 0) || data == NULL) return L; // for safety
for (unsigned i = 0; i < N; i += 1) insert(data[i], L);
return L;
}
This 3-line function just builds a List with the supplied vector of int
Complete C code
#include <stdio.h>
#include <stdlib.h>
typedef struct st_node
{
int data;
struct st_node* next;
} Node;
typedef struct
{
unsigned size;
Node* head;
Node* tail;
} List;
List* create();
List* destroy(List* toGo);
List* concat(List* one, List* other);
int display(List* list, const char* title);
int insert(int data, List* list);
int insert_sorted(int data, List* list);
List* merge(List* one, List* other);
List* build_list(unsigned N, const int data[]);
int main(void)
{
List* one = build_list(
10, (int[]){3, 4, 5, 7, 10, 15, 20, 25, 25, 30});
display(one, "'one'");
List* other = build_list(3, (int[]){2, 8, 9});
display(other, "'other'");
List* both = merge(one, other);
display(both, "merge(one,other)");
both = destroy(both);
both = concat(one, other);
display(both, "concat(one,other)");
one = destroy(one);
other = destroy(other);
both = destroy(both);
return 0;
}
List* build_list(unsigned N, const int data[])
{
List* L = create(); // new list
if ((N == 0) || data == NULL) return L; // for safety
for (unsigned i = 0; i < N; i += 1) insert(data[i], L);
return L;
}
List* create()
{
List* one = malloc(sizeof(List));
if (one == NULL) return NULL;
one->size = 0;
one->head = NULL;
one->tail = NULL;
return one;
};
List* destroy(List* gone)
{
if (gone == NULL) return NULL;
for (unsigned i = 0; i < gone->size; i += 1)
{
Node* p = gone->head->next;
free(gone->head);
gone->head = p;
}
free(gone);
return NULL;
};
int display(List* list, const char* title)
{
if (title != NULL) printf("%s", title);
if (list == NULL)
{
printf("\nList does not exist\n");
return 0;
}
printf("\nList size: %u\n [ ", list->size);
Node* p = list->head;
for (unsigned i = 0; i < list->size; i += 1)
{
printf("%d ", p->data);
p = p->next;
}
printf("]\n\n");
return 0;
};
List* concat(List* one, List* other)
{
if (one == NULL) return NULL;
if (other == NULL) return NULL;
List* res = create();
// copy 1st
Node* p = one->head;
for (unsigned i = 0; i < one->size; i += 1)
{
insert(p->data, res);
p = p->next;
};
// copy 2nd
p = other->head;
for (unsigned i = 0; i < other->size; i += 1)
{
insert(p->data, res);
p = p->next;
};
return res;
};
int insert(int data, List* list)
{ // insert at last element
if (list == NULL) return -1;
Node* p = malloc(sizeof(Node));
p->data = data; // data copied to node
p->next = NULL; // inserted at tail
if (list->size == 0)
{
list->head = list->tail = p;
list->size = 1;
return 0;
}
list->tail->next = p;
list->tail = p;
list->size += 1; // count it in
return 0;
}
int insert_sorted(int data, List* list)
{
// insert in position according to value
if (list == NULL) return -1;
Node* p = malloc(sizeof(Node));
p->data = data; // data copied to node
p->next = NULL; // inserted at tail
if (list->size == 0)
{
list->head = list->tail = p;
list->size = 1;
return 0;
}
Node* pos = list->head;
Node* prev = NULL;
while (pos->data < data)
{
if (pos == list->tail)
{ // new element is the greatest
pos->next = p;
list->tail = p;
list->size += 1;
return 0;
}
prev = pos;
pos = pos->next; // advance
}; // end while()
// 'pos' is the insertion point
if (pos == list->head)
{ // new head
list->head = p;
p->next = pos;
list->size += 1;
return 0;
}
// insert before 'pos'
prev->next = p;
p->next = pos;
list->size += 1; // count it in
return 0;
}
List* merge(List* one, List* other)
{ // returns a new sorted list with
// all values in the 2 input lists
if (one == NULL) return NULL;
if (other == NULL) return NULL;
List* mrg = create(); // new list
Node* p = one->head;
for (unsigned i = 0; i < one->size; i += 1)
{
insert_sorted(p->data, mrg);
p = p->next;
}
p = other->head;
for (unsigned i = 0; i < other->size; i += 1)
{
insert_sorted(p->data, mrg);
p = p->next;
}
return mrg; // result in new list
};
