In the following singly linked list, I am asked to show that \"whatever is the l

Question

In the following singly linked list, I am asked to show that "whatever is the length x of the intital of the initial segment before entering the loop and whatever is the length y of the loop itself, the above process will always find the point connecting the two parts. Provide a formal proof here."

Before this question I was asked to start with two pointers at the beginning of the list: one that moves step by step and another one that moves two steps at a time. Once the two pointers met on a node (in this case the blue circle), i had to put back the one that moved step by step at the beginning of the list and start moving again the two pointers but this time both in a step by step fashion until they meet again (in this case on the green pentagon).

Can anyone help with the question by giving a detailed explanation ? Thank you

Explanation / Answer

As i understand from tis question is called detect the loops inside a given list without breaking the links between the nodes..see the below code will detect the loops inside the list ..

It menas it used the concept slow pointer and speed pointer ..speed pointer always pointing to the next next node and slow pointer will point to the next node elemennt..

See the below code to understand the concept given in the problem statement.

/* This function detects loop in the list
If loop was there in the list then it returns 1,
otherwise returns 0 */
int detectAndRemoveLoop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;

while (slow_p && fast_p && fast_p->next)
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;

/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p)
{
//(slow_p, list);

/* Return 1 to indicate that loop is found */
return 1;
}
}

/* Return 0 to indeciate that ther is no loop*/
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.