Wednesday, August 11, 2010

Merging two sorted linked lists using c# (.Net)

The code itself isn't going to help copy+paste into your app, but it gives you an idea of how to go about merging two sorted linked lists (you can also pick up sorting a linked list if you are looking for that code). Feel free to post questions, comments and anything else that could be changed to make the code efficient and easier to understand.

Notes - This code was written in Visual Studio 2010 IDE, using .Net framework 3.5 (shoudln't be very different in other frameworks).Also to avoid simpler questions, it is a windows console application.


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MergeSortedLinkedList
{
class Program
{
static void Main(string[] args)
{
int[] arrInt=new int[]{17,65,96,97,112,133}; //defining arrays for the sake of example (sorted already)
int[] arrIntTwo = new int[] { 5, 77, 84, 99, 120, 155 }; //defining arrays for the sake of example (sorted already)
LinkedList lListOne = new LinkedList();//LinkedList declaration
LinkedList lListTwo = new LinkedList();//LinkedList declaration
//Append array one items to linked list one
foreach (int item in arrInt)
{
lListOne.AddLast(item);
}
//Append array two items to linked list two
foreach(int item in arrIntTwo)
{
lListTwo.AddLast(item);
}

//use flag to exit loop execution when condition is met
bool insertFlag=false;


int outLoopItem; //to hold the second list values
LinkedListNode outNode; //node for iteration

//Loop to iterate the second list and every time an item is moved from second list to first
// the second list item is removed using the lListTwo.Remove(outNode);
while(lListTwo.Count>0)
{
//since the lListTwo.Remove(outNode); is used to remove items from second list,
//the first item is the one to be picked always
outNode = lListTwo.First;
outLoopItem = outNode.Value;
insertFlag=false;
foreach(int inLoopItem in lListOne)
{
LinkedListNode inNode=lListOne.Find(inLoopItem);
if(outLoopItem<=inLoopItem && insertFlag==false)
{
lListOne.AddBefore(inNode,outLoopItem);
lListTwo.Remove(outNode);
insertFlag=true;
break;
}
}
if(insertFlag==false)
{
lListOne.AddLast(outLoopItem);
lListTwo.Remove(outNode);
}
}
Console.WriteLine("Sorted list");
foreach(int sortedList in lListOne)
{
Console.WriteLine("{0}", sortedList);
}
Console.Read();

}
}
}

No comments: