A Linked List, composed with structure elements and it is a linear data structure, and each elements are stored at different memory locations. Linked lists are good to add, inserts, subtract, delete each elements from this list. A Simple linked list example is given before in this Learn to Code Simple Linked List in Modern C++ on Windows post.
In present post we will explain how to sort two linked lists with a merge sort algorithm.
Let’s start a simple node for a linked list.
|
1 2 3 4 5 6 7 8 |
struct st_node { int value; struct st_node *next; }; struct st_node *head=NULL, *head1=NULL, *head2=NULL; |
We need a function that adds a new linked list member and return it’s address as a pointer. This add_new_link(…) function below will help to do this;
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
struct st_node * add_new_link(struct st_node **linkpoint) // we use ** to adress node { struct st_node *p = (struct st_node*) malloc(sizeof(st_node)); p->next=NULL; if(*linkpoint==NULL) // if it is null or begining set p itself { *linkpoint=p; // set linked as header } else if((*linkpoint)->next!=NULL) // if there is next link, insert this { struct st_node *swap=(*linkpoint)->next; (*linkpoint)->next=p; p->next=swap; // insert linked } else // if next link is null then append link to this { (*linkpoint)->next=p; // append linked } return(p); }; |
We need to delete all allocated lists from the memory, delete_linklist(…) function below will delete all nodes from the memory by a given header.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void delete_linklist(struct st_node** h) { struct st_node* current = *h; struct st_node* next; while (current != NULL) { next = current->next; free(current); current = next; } *h = NULL; } |
We can use Merge Sort algorithm to sort a linked list by a given header. When using Merge Sort function we should use Frontback Split algorithm in it, both can be written as below;
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
void frontback_split(struct st_node* source, struct st_node** frontRef, struct st_node** backRef) { struct st_node* fast; struct st_node* slow; slow = source; fast = source->next; while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } } slow->next = NULL; } void mergesort(struct st_node** headRef) { struct st_node* head = *headRef; struct st_node* a; struct st_node* b; /* Base case -- length 0 or 1 */ if ((head == NULL) || (head->next == NULL)) { return; } /* Split head into 'a' and 'b' sublists */ frontback_split(head, &a, &b); /* Recursively sort the sublists */ mergesort(&a); mergesort(&b); /* merge the two sorted lists together */ *headRef = sorted_merge(a, b); } |
If two linked list is sorted in their order we can combine both into one header pointer with this sorted_merge(..) function given below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
struct st_node* sorted_merge(struct st_node* a, struct st_node* b) { struct st_node* result = NULL; /* If one of paremeter is null retun the other one */ if (a == NULL) return (b); else if (b == NULL) return (a); /* take a or b and run recursevly */ if (a->value <= b->value) { result = a; result->next = sorted_merge(a->next, b); } else { result = b; result->next = sorted_merge(a, b->next); } } |
We can use this merge_sort_links() function to combine h1 and h2 headers to h header as given below;
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
void merge_sort_links(struct st_node **h1, struct st_node **h2, struct st_node **h) { struct st_node *p=NULL,*p1,*p2; p1=*h1; p2=*h2; if(p1->value<=p2->value) { *h=*h1; p=*h1; p1=p1->next; } else { *h=*h2; p=*h2; p2=p2->next; } do { if(p1!=NULL && p2!=NULL) { if( p1->value<=p2->value) { p->next=p1; p=p->next; p1=p1->next; } else { p->next=p2; p=p->next; p2=p2->next; } } else { if(p1!=NULL) { p->next=p1; p=p->next; p1=p1->next; } if(p2!=NULL) { p->next=p2; p=p->next; p2=p2->next; } } }while(p1!=NULL || p2!=NULL); } |
We can print all linked list members with this print_linkedlist() function starting from address at header pointer ;
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void print_linkedlist(struct st_node *start) { struct st_node *p=start; while(p!=NULL) { cout << p->value << "->"; p=p->next; }; cout << "\n"; } |
Finally, in the main() function of our application we can sort head1 and head2 with mergesort(…) function and we can combine both with merge_sort_links() functions as given below;
|
1 2 3 4 5 |
mergesort(&head1); mergesort(&head2); merge_sort_links(&head1, &head2, &head); |
