Assume you are working for an online shopping company (like Amazon) that uses a

Question

Assume you are working for an online shopping company (like Amazon) that uses a linked list to map orders for items placed online. Amazon seeks and hires consultants from a variety of satellite software companies to implement their code, which includes many incompetent programmers who tend to mess up pointers. To safeguard against such errors, you are asked to write a simple subroutine that checks for loops in a given list. Provide pseudo-code for a function that checks a linked list for loops. If it finds a loop, it is further required to eliminate the loop. You are made available a function getLength() which accurately returns to you the length of the list, and a pointer to the head of the list. In other words, you are required to implement void detectAndRemoveLoops()

Explanation / Answer

void detectAndRemoveLoop(Node *head)

{

Node *f1 = head;

Node *f2 = head ->next;

while(f2 && f2 -> next)

{

if(f1 == f2)

break;

f1 = f1 -> next;

f2 = f2 ->next ->next;

}

if(f1 == f2)

{

f1 = head;

while(f1 != f2 -> next)

{

f1 = f1 ->next;

f2 = f2 -> next;

}

f2 -> next = NULL;

}

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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