Q.1 How do you find whether there is a loop in a linked list? For example, the list in Figure bellow
contains a loop.
A list with a loop
www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community
A list with a loop
- This is a popular interview question. It can be solved with two pointers, which are initialized at the
head of list. One pointer advances once at each step, and the other advances 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 in bellow is implemented based on this solution. The faster pointer is pFast, and the slower one is pSlow.
C++ Code to Check Whether a List Contains a Loop
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; }Test Cases:
-
There is a loop in a list (including cases where there are one/multiple nodes in a
loop, or a loop contains all nodes in a list)
-
There is not a loop in a list
-
The input node of the list head is NULL
Q.
If there is a loop in a linked list, how do you get the entry node of the loop? The entry node is the first node in the loop from the head of a list. For instance, the entry node of the loop in the list of Figure bellow is the node with value 3.
A list with a loopwe can also solve this problem with two pointer.Two pointers P1 and P2 are initialized to point to the head of a list. If there are n nodes in the loop, the first pointer move forward n steps, and then two pointers move together with same speed. When the second pointer reaches the entry node of the loop, the first one travels around the loop and returns back to the entry node.Let’s take the list in Figure above as an example. P1 and P2 are first initialized to point to the head node of the list (Figure (a)). There are four nodes in the loop of the list, so P1 moves four steps ahead and reaches the node with value 5 (Figure (b)). Then these two pointers move two steps, and they meet at the node with value 3, which is the entry node of the loop, as shown in Figure (c).
Process to find the entry node of a loop in a list. (a) Pointers P1 and P2 are initialized at the head of list. (b) The pointer P1 moves four steps ahead since there are four nodes in the loop. (c) Both P1 and P2 move ahead till they meet at the entry node of the loop.
The only problem is how to figure out the number of nodes inside a loop. Let’s go back to the solution of the previous question. Two pointers are employed, and the faster one meets the slower one if there is a loop. The meeting node should be inside the loop. Therefore, we can move forward from the meeting node and count nodes in the loop until we arrive at the meeting node again.
The function Meeting Node in bellow code finds the meeting node of two pointers if there is a loop in a list, which is a minor modification of the previous HasLoop.
C++ Code to Get a Meeting Node in a Loop
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; }The function MeetingNode returns a node in the loop when there is a loop in the list. Otherwise, it returns NULL.
After finding the meeting node, it counts nodes in a loop of a list, as well as finding the entry node of the loop with the sample code, as shown inbellow code.
C++ Code to Get a Meeting Node in a Loop
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; }Test Cases:
-
There is a loop in a list (including cases where there are one/multiple nodes in a
loop, or a loop contains all nodes in a list)
-
There is not a loop in a list
-
The input node of the list head is NULL
-
There is a loop in a list (including cases where there are one/multiple nodes in a
loop, or a loop contains all nodes in a list)
-
There is a loop in a list (including cases where there are one/multiple nodes in a
loop, or a loop contains all nodes in a list)
