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.
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;
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.
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;
If two linked list is sorted in their order we can combine both into one header pointer with this sorted_merge(..) function given below.
We can use this merge_sort_links() function to combine h1 and h2 headers to h header as given below;
We can print all linked list members with this print_linkedlist() function starting from address at header pointer ;
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;