Some basic linked list problems
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 Removing duplicates from a sorted linked list.
Since the list is sorted ,we need to traverse it once. So here is the solution :
Remove Duplicates From Unsorted list
The same problem can be a bit modified when the linked list is not sorted. In this case , we need to traverse the list in order n2 times. There might be a better way to solve this but here is my solution for n2 complexity.
The next problem is to find the Mid Point of a linked list. This is a simple problem - only point we had to consider is to keep in mind that in case of an odd numbered list,we will return the midpoint where as in the case of an even numbered list,we will return node located at midpoint+1 position.The code goes here :
One of a very interesting problem is to find the nth element from last in a linked list. Now its very easy to find nth element from beginning of the list and can be done in one traverse. So what are the various solutions we can think of.
One of the methods involve traversing the list once to find the length say the length is l.
Now we need to find the mth element from last that means (l-m)th element from head so we need to traverse the list once again till we reach (l-m)th element.
This method is good for small lists where number of elements to be traversed are not large but if the number is large then there would be a problem since there would be twice the traversal.
Other method is to hold a pointer to a node which is m nodes ahead and traverse the list till the node reaches last so the node which is m nodes behind is the desired node.
The code for this algorithm is below :
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 Reversing a list .
The next problem is Removing duplicates from a sorted linked list.
Since the list is sorted ,we need to traverse it once. So here is the solution :
Remove Duplicates From Unsorted list
The same problem can be a bit modified when the linked list is not sorted. In this case , we need to traverse the list in order n2 times. There might be a better way to solve this but here is my solution for n2 complexity.
One of a very interesting problem is to find the nth element from last in a linked list. Now its very easy to find nth element from beginning of the list and can be done in one traverse. So what are the various solutions we can think of.
One of the methods involve traversing the list once to find the length say the length is l.
Now we need to find the mth element from last that means (l-m)th element from head so we need to traverse the list once again till we reach (l-m)th element.
This method is good for small lists where number of elements to be traversed are not large but if the number is large then there would be a problem since there would be twice the traversal.
Other method is to hold a pointer to a node which is m nodes ahead and traverse the list till the node reaches last so the node which is m nodes behind is the desired node.
There is a one more solution in which we don't have to as much traversing as we had done above.This is a bit complicated but interesting. In it we traverse the list in rounds of n nodes and maintain a pointer to the node which is beginning of the node which is m nodes behind the beginning of current node. e.g. if a list has 10 elements and the elements are 1-2-3-4-5-6-7-8-9-10 and we need to find the 4th element from last i.e. 7 we would proceed the list in a set of 4 elements so that when current reaches 5th node, pointer is at 1st node.When it reaches 9th node ,pointer is at 5th node.After 9th node we get to the last node in 2 turns so mth node will be 5+2 i.e. 7th node .The code to implement this is as follows :
MergeWithItself is not working when assign head to current , head is always null. can't finish the while.
ReplyDeletethanks a bunch
in the removeduplicate method of sorted list its showing me an exception of null reference in this statement
ReplyDeletewhile (current.next != null)
please help asap
This comment has been removed by the author.
ReplyDeletepublic void delete(object Item)
ReplyDelete{
Node pointer = head;
Node temp;
if (head.Data.ToString() == Item.ToString())
{
head = head.next;
}
else
{
while(pointer.next != null)
{
if(pointer.next.Data.ToString() == Item.ToString())
{
temp = pointer.next;
pointer.next = temp.next;
break;
}
pointer = pointer.next;
}
}
display();
}