Question 1:
How to check whether there is a loop in a linked list? For example, the list in
Figure 1 has a loop.
Figure 1: A list with a loop |
A node in list is defined as the following structure:
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};
Analysis:
It is a popular interview question. Similar to the problem to get the Kth
node from end is a list, it has a solution with two pointers.
Two pointers are initialized at the head of list. One
pointer forwards once at each step, and the other forwards twice at each step.
If the faster pointer meets the slower one again, there is a loop in the list. Otherwise
there is no loop if the faster one reaches the end of list.
The sample code below is implemented according to this
solution. The faster pointer is pFast, and the slower one is
pSlow.
bool
HasLoop(ListNode* pHead)
{
if(pHead ==
NULL)
return false;
ListNode* pSlow = pHead->m_pNext;
if(pSlow ==
NULL)
return false;
ListNode* pFast = pSlow->m_pNext;
while(pFast
!= NULL && pSlow != NULL)
{
if(pFast
== pSlow)
return
true;
pSlow = pSlow->m_pNext;
pFast = pFast->m_pNext;
if(pFast
!= NULL)
pFast = pFast->m_pNext;
}
return false;
}
Question 2:
If there is a loop in a linked list, how to get the entry node of the loop? The
entry node is the first node in the loop from head of list. For instance, the
entry node of loop in the list of Figure 1 is the node with value 3.
Analysis:
Inspired by the solution of the first problem, we can also solve this problem
with two pointers.
Two pointers are initialized at the head of a list. If there
are n nodes in the loop, the first
pointer forwards n steps firstly. And
then they forward together, at same speed. When the second pointer reaches the
entry node of loop, the first one travels around the loop and returns back to
entry node.
Let us take the list in Figure 1 as an example.
Two pointers, P1 and P2 are firstly initialized at the head node of the list
(Figure 2-a). There are 4 nodes in the loop of list, so P1 moves 4 steps ahead,
and reaches the node with value 5 (Figure 2-b). And then these two pointers
move for 2 steps, and they meet at the node with value 3, which is the entry
node of the loop.
The only problem is how to get the numbers in a loop. Let go
back to the solution of the first question. We define two pointers, and the
faster one meets the slower one if there is a loop. Actually, the meeting node
should be inside the loop. Therefore, we can move forward from the meeting node
and get the number of nodes in the loop when we arrive at the meeting node
again.
The following function MeetingNode
gets the meeting node of two pointers if there is a loop in a list, which is a minor modification of the previous HasLoop:
ListNode*
MeetingNode(ListNode* pHead)
{
if(pHead ==
NULL)
return
NULL;
ListNode* pSlow = pHead->m_pNext;
if(pSlow ==
NULL)
return
NULL;
ListNode* pFast = pSlow->m_pNext;
while(pFast
!= NULL && pSlow != NULL)
{
if(pFast
== pSlow)
return
pFast;
pSlow = pSlow->m_pNext;
pFast = pFast->m_pNext;
if(pFast
!= NULL)
pFast = pFast->m_pNext;
}
return
NULL;
}
We can get the number of nodes in a loop of a list, and the
entry node of loop after we know the meeting node, as shown below:
ListNode* EntryNodeOfLoop(ListNode*
pHead)
{
ListNode* meetingNode = MeetingNode(pHead);
if(meetingNode
== NULL)
return
NULL;
// get the number
of nodes in loop
int
nodesInLoop = 1;
ListNode* pNode1 = meetingNode;
while(pNode1->m_pNext
!= meetingNode)
{
pNode1 = pNode1->m_pNext;
++nodesInLoop;
}
// move pNode1
pNode1 = pHead;
for(int i = 0; i < nodesInLoop; ++i)
pNode1 = pNode1->m_pNext;
// move pNode1
and pNode2
ListNode* pNode2 = pHead;
while(pNode1
!= pNode2)
{
pNode1 = pNode1->m_pNext;
pNode2 = pNode2->m_pNext;
}
return
pNode1;
}
The discussion about these two problems is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of this post. If you are going
to use part of or the whole of this ariticle in your blog
or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.
It took me about two hours to figure this thing out. I never delved into pointers... What confused me the most is in part two. I was wondering where did you get numbers in a loop (4) and then i saw it down. I got this thing. Quality text.
ReplyDeleteI think it is not necessary to get the number of nodes in a loop of a list. Firstly, we initialize pslow and pfast the head of list. The pslow pointer forwards once at each step, and the pfast forwards twice at each step. If the pfast pointer meets the pslow pointer , then wo set the pslow the head of list, the pfast is still at the node where they meet. Then the pslow and pfast pointer forwards once at each step,the entry node of the loop is the node where the two pointer meet again. I saw the solution is at the blog http://blog.csdn.net/hackbuteer1/article/details/7583102
ReplyDeleteHello Sir, In Question-1, why you use two condition in while loop
ReplyDeletewhile(pFast != NULL && pSlow != NULL)?
while(pFast != NULL) will be sufficient. Because if there is no loop then pFast will reach more quickly.
Will above algo work if Node 6 loop back to Node 2?
ReplyDeleteThis is not correct solution
typedef struct node {
ReplyDeleteint data;
struct node *next;
} node;
typedef struct linked_list {
int count;
node *head;
} linked_list;
node * ll_hasloop(linked_list *ll)
{
node *fast = NULL, *slow = NULL;
if (ll && ll->head) {
fast = slow = ll->head;
while (fast) {
slow = slow->next;
fast = fast->next;
if (fast) {
fast = fast->next;
}
if (slow == fast) {
break;
}
}
}
return fast;
}
node * ll_hasloop_loopstart(linked_list *ll);
{
node *meet = NULL, *start = NULL;
meet = ll_hasloop(ll);
if (meet) {
while (meet != start) {
meet = meet->next;
start = start->next;
}
}
return start;
}
check this for c# interview questions
ReplyDelete@ http://skillgun.com
Hi Harry, Why does the faster pointer move twice only. What is the best ratio between faster and slower pointer?
ReplyDeleteWithout loss of generality, let's assume cycle size if C and nodes of cycle are numbered from 0, 1, ..., C -1, 0 and both pointers start from 0 and let's say they both meets after N operations, then
DeletejsFast * N mod C = jsSlow * N mod C
N = C (q1 - q2)/(jsFast - jsSlow)
In order to have a valid N, denominator should divide numerator. In general, we can't say anything about it unless jsFast - jsSlow is equal to 1.
So, jump size can be anything but there should be unit difference in jump sizes.
Its simply superb.Feeling good to share the link to practice
ReplyDeletec# interview questions @ http://skillgun.com
Thank you sharing this Information
ReplyDeleteI also found Various useful links related to Devops, Docker & Kubernetes
Kubernetes Kubectl Commands CheatSheet
Introduction to Kubernetes Networking
Basic Concept of Kubernetes
Kubernetes Interview Question and Answers
Kubernetes Sheetsheat
Docker Interview Question and Answers
Docker Basic Tutorial
Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
ReplyDeletepython internship | web development internship |internship for mechanical engineering students |mechanical engineering internships |java training in chennai |internship for 1st year engineering students |online internships for cse students |online internship for engineering students |internship for ece students |data science internships