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.