Linked List and few questions on them

Linked-List: Linked-List is a group of nodes.  Where each Node is made of two parts.  The first part contains the data, and the second holds pointer, which refers to the Node.

Note: The term first part is a logical term, we can have any number of data types, but the second part should contain only one pointer, which is used to point next Node.

Below is the image depicting the concept:

Here A,B,C,D are assumed to be addresses of the Nodes,  which of course would be in some Hexadecimal form.  Values 12,25,65,19 are assumed data.  In fact we could have a Node with 3 or more partitions with all the partitions holding data except one, which is reserved for a pointer to hold next node address.  The last node of a linked list should hold null as value in address pointer.

With this basics lets move to solve few interesting questions on Linked List.

Question 1: Given a LinkedList ll, find the middle node.  

Solution(1): Iterate through the linked list and count the number of nodes say 'n'.  Again iterate the linked list from the head for n/2 times and return the middle node.

code snippet:
head=ll;
temp=ll;
int n=0;
while(temp!=null){
 temp=temp->next;
 n++;
}
temp=ll;
for(int i=0;i<n/2;i++)
 temp=temp->next;
return temp;

Time Complexity: θ(n).

Solution(2):  We'll look at well know and a very important logic (Slow moving, fast moving pointers ---> Tortoise - Hare algorithm  ). Here  well use two pointers let they be 'fast' and 'slow' for every single move of slow pointer we'll move the fast pointer twice.  Thus once the fast moving pointer reaches the null (end of linked list), we can say that the slow pointer reached to the middle of the linked list.

Code snippet:
fast=ll;
slow=ll;
while(fast!=null){
//if the no. of nodes are odd in no., 
//we can't iterate twice at the last node.
 if(fast->next=null)
    fast=fast->next;
 else
    fast=fast->next->next;  // for every other position we can iterate twice.
slow=slow->next;
}
return slow;

Time Complexity: θ(n)

Question(2):  Given two linked-lists find if they meet each other.  Image below should give us what the question is asking us to find.

Given here are two linked lists L1 and L2 with different paths.  But they are found meeting at node C.  The solution is to find that C and returning it.

Solution(1): Traverse through L1 and add each element in a HashSet.  Now iterate through L2 either till we meet either of 2 conditions.

1. Node in L2 found in HashSet.

2. End of L2 is reached ( i mean we reached null pointer while traversing ).

(Here I would like to jump to java code, please don't mind).

code snippet:

HashSet hs=new HashSet(L1.size());

Iterator i1t=L1.iterator();

while(it1.hasNext())

 hs.add(it1.next());

Iterator it2=L2.iterator();

while(it2.hasNext()){

 Object o=it2.next();

 if(hs.contains(o))

   return o;

}

return null;

Time Complexity:  θ(n)

Solution 2: 

Imagine if we have the two list of same size.  Then it would be sufficient to compare each nodes from both the list and if they are not found equal we'll go ahead traversing both the list at a time, and compare the new nodes again.  This is done till we reach a node that is common to both the lists.  

But unfortunately we might be given list of different sizes.  We'll simply take down the lengths  of both the lists and we'll traverse the longer list till the length of longer list is equal to the shorter one.  Thus we'll end-up having lists of equal lengths.

Code snippet:

x=length(l1);

y=length(l2);

while(x!=y)

   l1=l1->next;

while(y!=x)

  l2=l2->next;

while(l1!=l2){

 l1=l1->next;l2=l2->next;

}   

return l1;

Time Complexity: O(n)

Question (3): Find weather there is a loop in the given LinkedList and rectify the list.

Explanation:  If the given linked list is as shown in the image below:

We can see clearly that the node D is connect back to node B(a loop), the question expects us to rectify this case.

Thus the issue first is to find weather any such element exists which points back to any element which is already the part of linked-list.  If such node exists we'll make it point to null.  Thus making the linked-list look like:

Solution(1):  Initialize a HashSet and start inserting each node into the HashSet, while inserting check if it already exists in the HashSet, If it does exists make to the previous node's pointer point to null.

Time Complexity: O(n)

Space Complexity: θ(n)  ---------------> for hashset.

Solution(2):  This can be solved using Tortoise-Hare algorithm.  In this case we'll first find if there is a loop in the given linked list.  If it's present we'll rectify that.

step1 (to find if the loop exists):  We'll use 2 pointers a namely fast and slow.  For every step of slow pointer we'll move fast pointer 2 steps.  If there is a loop, fast pointer will meet the slow pointer at its next 2nd or 3rd loop.  If the fast pointer ends with null as next to point, we can say that the loop doesn't exists.

step2 (if the loop exists, we need to find the length of the loop): Once the two pointers found meeting, we'll stop a pointer and move the other pointer, we'll count the number of steps the moving pointer takes to catch up the pointer which is at rest.  The count is the length of the loop.  Let the count be in the variable 'c'

Step 3(Fixing the linked-list): Fix slow pointer at the head, and the fast pointer at distance 'c' from the slow pointer.  Start moving both the pointers, interestingly both these pointers will meet at the beginning of the loop.  By the way we'll follow fast moving pointer with a temp pointer with one step lag.  Once fast and slow pointers meet. We can disconnect the loop by pointing temp->next pointer to null.  (In case you guys needs little more clarity, we shall have a image explaining this.  Please post a comment in that case.)

Code snippet:

fast=ll;

slow=ll;

while(fast!=slow){

 if(fast==null) return null; // If no loop exists return null;

 fast=fast->next;   // move fast once

 if(fast=null)return null;  // If no loop exists return null;

 fast=fast->next;  // move fast again

 slow=slow->next; // move slow once

 if(fast==slow)break;   // fast meeting slow

}

//we reach here only if there is a loop

int c=0;  //count variable to find the length of the loop.

fast=fast->next // move only fast pointer, keeping slow pointer at rest.

while(fast!=slow){

c++;

fast=fast->next;

}

slow=ll;// fix slow at head location

fast=ll;

for(int i=0;i<c;i++) // traverse fast till the distance between slow and fast is 'c'.

 fast=fast->next;

prev=fast; // prev pointer follows fast pointer with one step lag.

fast=fast->next;

slow=slow->next;

while(slow!=fast){

 prev=prev->next;

 fast=fast->next;

 slow=slow->next;

}

prev->next=null.

Time Complexity: O(n).