Searching in a linked list
August 10, 2012check if all nodes of a tree has only one child
August 18, 2012Detecting loop in a linked list
Given a Singly linked list which may contain a loop (link of last node pointing to some Node in the list). Write code to detect the loop.
Traverse the list till the end (Incorrect Solution).
If there is a loop in the list, then there is no end, we never know when we have reached the repeating value (unless we are marking the nodes).
Detecting only Full Loop (Incomplete Solution).
Sometimes, The first approach is to traverse the list using a temporary pointer untill it becomes null or becomes equal to the head pointer.
If it becomes equal to head pointer, there is a loop. If it becomes NULL, there is no loop.
The Flaw in this approach is that it will only detect the loop if the last node is pointing to the first node. It will not detect intermediate loops (as shown in the picture above).
Brute-Force Method:
For each Node, traverse the entire list from the start till the previous Node and see if there is a Node which is equal to the current Node. If yes then we have detected a loop, else continue.
It is like checking the entire list we have traversed so far. This method will take O(n2) time.
Marking the visited Nodes
Marking can be done in two ways
1. Using hash table to store the Nodes which are visited.
Traversing the list. For each Node
If the Node is present in the Hash table
Loop detected
Else
Store the Node in Hash Table and move forward
2. Keeping an extra field per node. Structure of the Node will be
struct Node
{
int data;
Node* link;
bool visited;
};
Initially all the nodes will visited=false.
Traversing the list. For each Node
If visited of the Node is true
Loop detected
Else
set node.visited=true and move forward
Both of these methods will require O(n) extra space.
Reversing the list
Don’t change pointer to the head Node. Reverse the list.
If there is a loop in the list you will reach the head node itself while reversing the list.
If you don’t reach the head Node there is no loop in the list.
This is an O(n) time algorithm and requires O(1) extra space. But you need to reverse the list twice, first to detect the loop and then to restore the original list. Hence the constant factor of time is large.
Using Two Pointers (Best Algorithm)
This is also called “Tortoise & Hare Algorithm“, In this algorithm we traverse the list simultaneously using a fast pointer and a slow pointer. If there is a loop the two will become equal:
1. take two pointers ptrSlow and ptrFast both pointing to head node 2. While (ptrSlow != ptrFast and ptrFast != NULL) - increment ptrSlow by one Node (ptrSlow = ptrSlow->link) - increment ptrFast by two Node (ptrFast = ptrFast->link->link)
Code:
bool detectLoop(Node *head)
{
Node* slowPtr = head;
Node* fastPtr = head;
while(fastPtr != NULL && fastPtr->link != NULL )
{
slowPtr = slowPtr->link;
fastPtr = fastPtr->link->link;
if (slowPtr == fastPtr)
return true;
}
return false;
}
Note: If it is a doubly linked list then one more solution can be to check backward (using previous pointer to see it this node is present in the already traversed list).
13 Comments
Using Two Pointers (Best Algorithm)
It is completely wrong solution.Please recheck it.
I was pretty pleased to uncover this page. I
need to to thank you for ones time due to this
fantastic read!! I definitely loved every part of it and I have
you saved as a favorite to look at new information on your
website.
When someone writes an article he/she retains the thought of a user in his/her
brain that how a user can be aware of it. Therefore that’s why this piece of
writing is great. Thanks!
Unquestionably consider that that you stated. Your favourite justification seemed to
be at the internet the easiest factor to take into account of.
I say to you, I definitely get irked whilst other people think
about worries that they just don’t know about. You managed to hit the nail upon the highest
as neatly as outlined out the entire thing with no need side effect ,
people could take a signal. Will likely be again to get more.
Thanks
Thanks for sharing your thoughts about Interview Questions.
Regards
Can you tell us more about this? I’d care to find out some additional information.
Share survey results with your managers and employees and
communicate next steps. A code of ethics takes care of these violations,
which have caused spectacular scandals in the history of baseball.
North Port High School will have a new basketball coach.
Hi, its nice piece of writing about media print, we all know media
is a great source of facts.
Humana People to People gets the purpose
to develop under-developed countries around the world by providing teaching to primary school instructors and tradesmen, assisting to promote
good health and give knowledge about Aids as well as to assistance in extra rising the places agriculture.
Humana People to People assumes numerous various projects
and missions around poor regions of nations globally.
By way of cooperating with the nearby persons along with governing administration, they’re able to aid individuals who
are in need of funds thru their non-profit aid corporations.
China is one kind of many countries that this non-profit agency goes to face the driving issues which they confront now.
The Humana People to People Activity works jointly with The Federation for Organizations within the Yunnan province
of China. The job first began during 2005 and carries on around today.
The Humana People to People Association Work
Office of the Yunnan Province operates to boost money to execute
diverse tasks all through the province around poverty-stricken locations.
A few plans which Humana People to People seeks to take to
this region of China involve vocational instruction centers in which they can expand their education and learning, planning
them to get jobs, giving information on transmittable sicknesses and
many more.
Humana People to People first began carrying out their commissions within China during 2007.
One of the initial projects that was assumed was the Malaria plan which targeted to
deliver useful facts and avoidance about the condition to location residents.
A Group Capability Progression and Child Aid plan was afterward started in Zhenkang.
An amazing 13 tasks were started in 2010 for some from the biggest poor areas
of the region. Beyond just the Yunnan Province, projects
were got going in the Sichuan Province, Chongqing Area
and Guangdong Province.
Presently, a number of commissions that Humana has assumed within China involves treatment in non-urban locations, earlier youthful instruction that is developed to provide Chinese children a lead on their way to
achievement, generating safer paths for Humana preschool children, supplying fast HIV testing, starting
grower organizations and improving funds by nonprofit events for example the Comedy Pub China Charity Show.
Currently, there are 11 developments currently being accomplished all over 3 provinces in China
and in a lot more than 128 communities. Along with 280 collective beneficiaries, People to
People gives expect and also a better future to these poverty-stricken countryside places.
It is not my first time to visit this web site, i am browsing this web site
dailly and get pleasant information from here everyday.
Fastidious respond in return of this issue with solid arguments and telling the whole thing on the topic of that.
Very quickly this website will be famous among all blogging and site-building visitors, due to it’s nice content
Keep on working, great job!