Introduction
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.
How to merge LinkedList?
However, in C#, we already have a LinkedList class under System.Collections.Generic namespace, it is always good to build it from the ground up since it helps in understanding fundamentals. Now a singly linked list is a collection of nodes where one node points to another and the last one points to null. Though there is no concept of pointers in C#, internal addresses are managed through pointers only.
So let's define a simple Node class.
public class Node
{
public object data;
public Node next;
public Node(object data)
{
this.data = data;
}
}
The Node class is a very simple class that contains some data and has an element Node that points to the next node.
A linked list will be simply a collection of these nodes.
Let's define it also.
public class LinkedList
{
Node head;
Node current;
public Node Head //Expose a public property to get to head of the list
{
get { return head; }
}
public void Add( Node n)
{
if (head == null)
{
head = n; // point head to first added node
current = head; // set current to head
}
else
{
current.next = n; //Set current next to newly added node.
current = current.next; //Set new current to current next.
}
}
}
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 the 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 the first and another one as the second
e.g. For the above cases of list first list would be 1-3-5..... and the second one would be 5-7-8.. if the lists 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 that had the smallest element at its head and then compare it with elements of the second list till we find some element in the second that is smaller than the current element in the first list. If we find that element, then that is removed from the second and inserted in the first after the current element.
If the first list ends and there are still some elements in the second list, then we simply point the next current to the current of the second since the elements would already be in a sorted position in both lists.
Also, it would be more clear if a diagram could be made out of this algorithm.
The code for the above algorithm is below and is self-explanatory.
public void MergeSortedList(Node first,Node second)
{
// We would be always adding nodes from the second list to the first one
// If second node head data is more than first one exchange it
if (Convert.ToInt32(first.next.data.ToString())
> Convert.ToInt32(second.data.ToString()))
{
Node t = first;
first = second;
second = t;
}
head = first; //Assign head to first node
//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.
while ((first.next != null) && (second != null))
{
if (Convert.ToInt32(first.next.data.ToString())
<Convert.ToInt32(second.data.ToString()))
{
first = first.next; //Iterate over the first node
}
else
{
Node n = first.next;
Node t = second.next;
first.next = second;
second.next = n;
first = first.next;
second = t;
}
}
if (first.next == null) // Means there are still some elements in second
first.next = second;
}
To test it write a simple console application and test it for every case. The console application test would be like this.
static void Main()
{
LinkedList l1 = new LinkedList();
//l1.Add(new Node("1"));
l1.Add(new Node("2"));
l1.Add(new Node("3"));
l1.Add(new Node("4"));
l1.Add(new Node("5"));
l1.Add(new Node("8"));
l1.Add(new Node("100"));
l1.Add(new Node("120"));
LinkedList l2 = new LinkedList();
l2.Add(new Node("10"));
l2.Add(new Node("30"));
l2.Add(new Node("34"));
LinkedList list = new LinkedList();
list.MergeSortedList(l1.Head,l2.Head);
list.PrintNodes();
Console.ReadLine();
}
Print Nodes is a simple function that 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 a linked list. To understand the 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.