Merging of linked lists

In this article ,I will be discussing some problems based on merging of linked lists.


Problem statement : We had 2 linked lists - a1-a2-a3.....aN and b1-b2-b3..........bN
We want to merge it into a single linked list - a1-b1-a2-b2-a3-b3...........an-bn



Solution : We would be using the linked list we had already developed in previous blogs. I am again showing the structure of this list below :

There would be a simple function in this list which takes 2 nodes and merges them both into the main linked list.The given function is :
The simple strategy here is to iterate through the 2 lists and keep on adding current node of of each list to the original linked list. Below is a test program to test it.
One variation of the above problem could be to write a function in LinkedList class which accepts a linked list and merges it with itself.


Problem statement : Merging of 2 sorted linked lists. Given 2 sorted single linked lists -
first : 1-2-3-4-5-8-100-120
second : 5-7-11-34-109-130
Final : 1-2-3-4-5-5-7-8-34-100-109-120-130


Solution : The given problem can be solved by comparing each node of first list with second one and inserting nodes from second to first where ever there is a need. e.g. in the above example 5- in second node is inserted between 5-8 in first node.The code follows below :


The above problem can also be solved by simple merging as first-->next = second node and then sorting it,though sorting would be an expensive operation.In the next few articles we will see how sorting can be performed efficiently using linked lists.



Comments

  1. JayathuFebruary 25, 2013 at 5:38 PM

    Your solution for MergeSort works great in most cases where the lists have more than two nodes in them. It breaks however, when the lists have less than two nodes. You might want to address them as special cases in your algorithm;

    ReplyDelete
  2. UnknownAugust 22, 2013 at 11:56 PM

    Hi,Nice solution for MergeSort of linked lists in c#.Iam interested in the above code.Its very useful for me to test the program.Thanks..

    -Aparna
    Theosoft

    ReplyDelete

Post a Comment

Popular posts from this blog

Simple linked list implementation in C#

Image
Linked list is the most basic data structure taught in the colleges.Though it looks simple,the kind of complex problems we can solve through it is just amazing.In languages like C,C++ its very easy to understand though pointers.Unfortunately or fortunately in C#,we don't need pointers to learn about linked list though internally,its all pointers all the way to the memory addresses.In this post I will try to explain how a link list can be implemented in C#. Ok,enough of technical jargon.Lets come straight to the point. Definition : A linked list is a simple chain of nodes where a node points to next node and so on till the next node doesn't points to anything. Now what is a node? A node is a simple object which contains some data and a reference to next node.Lets code both our node and linked list class. The Node class is self explanatory. As we can see the Linked List class just contains a head node and all the nodes are added to this node. A little bit of explanat
Read more

Some basic linked list problems

Image
In my earlier  post  , we had seen how to implement a basic linked list in C#. We also saw both stack and queue based additions to the linked list. In this post we are going to look at some of the basic linked list problems which will prepare us for more adventure ahead.We will start with basic node class. We would keep adding functions in the LinkedList class as we program. Right now the list is empty with only 2 nodes- head and current which both point to null.Below I am giving the code for simple insertion and printing of nodes,once they are added. Below I am giving code for some functions which can be added to this class. These are : Node Find Find a node in the list.It returns the node when it is found.If the corresponding node is not found null is returned. The next problem is to remove a node from the list. Here we would create a small helper function which would return a previous node. The given functions are below : The next problem is Reversing a list . The next
Read more

Composition over Inheritance

We had often heard that composition is better than inheritance. Why is it so? First of all how is one different from the other and what are the similarities in them? Lets say we are writing simulation software for Rocket Launching systems which are to be supplied to different countries. Now these different countries can use them as they want it. The code for our launching system is below: public   class   Launcher {      public   bool  LaunchMissile()     {          Console .WriteLine( "Missile launched" );          return   true ;     } } public   class   SufraceToAirMissileLauncher : Launcher {   } Now, country A uses this code to launch missile as follows: static   void  Main( string [] args)     {          SufraceToAirMissileLauncher  staLauncher =  new   SufraceToAirMissileLauncher ();          bool  isLaunched =   staLauncher.LaunchMissile();     } This is how Inheritance is used. The various launchers can reuse the base Launcher class code to launch m
Read more