Merging Two Sorted Linked Lists In C#

In this article, I am going to explain how to merge 2 sorted linked lists. We are given 2 sorted linked lists and we had to merge them into one such that the final list is also a sorted one.

Though in C#, we already have a LinkedList class under System.Collections.Generic namespace, it is always good to build it from ground up since it helps in understanding fundamentals. Now a singly linked list is a collection of nodes where node points to another and the last one points to null. Though there is no concept of pointers in C#, internally addresses are managed through pointers only.

So lets define a simple Node class.
  1. public class Node  
  2. {  
  3.    public object data;  
  4.    public Node next;  
  5.    public Node(object data)  
  6.    {  
  7.        this.data = data;              
  8.    }  
  9. }  
The Node class is a very simple class which contains some data and has an element Node which points to next node.

A linked list will be simply a collection of these nodes. 
 
Let's define it also:
  1. public class LinkedList  
  2. {  
  3.     Node head;  
  4.     Node current;  
  5.     public Node Head //Expose a public property to get to head of the list  
  6.     {  
  7.         get { return head; }  
  8.     }  
  9.     public void Add( Node n)  
  10.     {  
  11.         if (head == null)  
  12.         {  
  13.             head = n; // point head to first added node  
  14.             current = head; // set current to head  
  15.         }  
  16.         else  
  17.         {  
  18.             current.next = n; //Set current next to newly added node.  
  19.             current = current.next;  //Set new current to current next.  
  20.         }  
  21.     }  
  22. }  
This linked list class has 2 nodes- head and current. Node head points to the beginning of a list and current denotes the current node in the list chain. Also, we had a public method Add() which adds a node to the end of the linked list.
 
Now coming to the problem. We had 2 sorted linked lists and we had to merge them into one which again should be sorted.
 
e.g. say first list is 1-3-5-6-8-10 and other is 5-7-8-9-15-20 then final list should be 1-3-5-5-6-7-8-9-10-15-20
 
There can be many ways to do this but here we will be focussing on merging only. The way we would be progressing is to write a function in LinkedList class which takes 2 nodes and returns the final merged list. A small pseudo algorithm for the above solution would be:
 
Find out which list's head is less. Assign that list as first and another one as the second 
 
e.g. in the above cases of list first list would be 1-3-5..... and the second one will be 5-7-8.. if the lists would have been 3-5-6-8-10 and 2-5-7-8-9..... then we would have assigned 2-5-7...as first and another one as the second.
 
So, the idea is to iterate over the list which had the smallest element at its head and then comparing it with elements of the second list till we find some element in second which is smaller than the current element in first list. If we found that element then that is removed from the second and inserted in first after the current element.
 
If the first list ends and there are still some elements in the second list then we simply point next of current to current of second since the elements would already be in sorted position in both lists.
 
Also it would be more clear if a diagram can be made out of this algorithm.
 
The code for above algorithm is below and is self explanatory.
  1. public void MergeSortedList(Node first,Node second)  
  2. {  
  3.     // We would be always adding nodes from the second list to the first one  
  4.     // If second node head data is more than first one exchange it  
  5.     if (Convert.ToInt32(first.next.data.ToString())  
  6.             > Convert.ToInt32(second.data.ToString()))  
  7.     {  
  8.         Node t = first;  
  9.         first = second;  
  10.         second = t;                
  11.     }  
  12.     head = first; //Assign head to first node  
  13.     //We need to assign head to first because first will continuosly be changing and so we want to store the beginning of list in head.  
  14.     while ((first.next != null) && (second != null))  
  15.     {  
  16.         if (Convert.ToInt32(first.next.data.ToString())  
  17.             <Convert.ToInt32(second.data.ToString()))  
  18.         {  
  19.             first = first.next; //Iterate over the first node  
  20.         }  
  21.         else  
  22.         {  
  23.             Node n = first.next;  
  24.             Node t = second.next;  
  25.             first.next = second;  
  26.             second.next = n;  
  27.             first = first.next;  
  28.             second = t;  
  29.         }  
  30.     }  
  31.     if (first.next == null// Means there are still some elements in second  
  32.         first.next = second;             
  33. }  
To test it write a simple console application and test it for every case. The console application test would be like this:
  1. static void Main()  
  2. {  
  3.     LinkedList l1 = new LinkedList();  
  4.     //l1.Add(new Node("1"));  
  5.     l1.Add(new Node("2"));  
  6.     l1.Add(new Node("3"));  
  7.     l1.Add(new Node("4"));  
  8.     l1.Add(new Node("5"));  
  9.     l1.Add(new Node("8"));  
  10.     l1.Add(new Node("100"));  
  11.     l1.Add(new Node("120"));  
  12.   
  13.    
  14.     LinkedList l2 = new LinkedList();  
  15.     l2.Add(new Node("10"));  
  16.     l2.Add(new Node("30"));  
  17.     l2.Add(new Node("34"));  
  18.     LinkedList list = new LinkedList();  
  19.     list.MergeSortedList(l1.Head,l2.Head);  
  20.     list.PrintNodes();  
  21.     Console.ReadLine();  
  22. }  
Print Nodes is a simple function which prints the data value of each node in the list. I am leaving it up to you to implement this function.
 
The linked list may seem to be a simple data structure but the kind of complexity it can offer is amazing. In this article, we saw a simple merging function for linked list. To understand linked list better we can again solve the following problems:
  • Merge alternate elements of 2 linked lists e.g. 1-4-7-10 and 3-5-6-6 should be  merged as 1-3-4-5-7-6-10-6
  • Merge 3 sorted linked lists or merge n sorted linked lists.
  • Sort a linked list 
I am again leaving it up to you to explore the hidden treasures of your brain.