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,its 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.
public class Node
{
public object data;
public Node next;
public Node(object data)
{
this.data = data;
}
}
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.
Lets 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 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 other one as second
e.g. in the above cases of list first list would be 1-3-5..... and 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 other one as second.
So,the idea is to iterate over the list which had smallest element at its head and then comparing it with elements of second list till we find some element in second which is smaller than 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 first list ends and there are still some elements in the second list then we simple 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.
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 which prints the data value of each node in the list. I am leaving it upto you to impplement this function.
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 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.