A linked list contains a cycle if, starting from some node p, following a suffic

Question

A linked list contains a cycle if, starting from some node p, following a sufficient number of next links brings us back to node p. p does not have to be the first node in the list. Assume that you are given a linked list that contains N nodes. However, the value of N is unknown.

A. Design an O(N) algorithm to determine if the list contains a cycle. You may use O(N) extra space.

B. Repeat part (a), but use only O(1) extra space. (Hint: Use two iterators that are initially at the start of the list, but advance at different speeds.) (No program needed, pseudo code is fine).

Explanation / Answer

Algorithm:

Linked List Each node has two parts 1) data--contains the value 2) Next--pointer o the next node in the list
  

Have two pointers iterating through the list; make one iterate through at twice the speed of the other,
and compare their positions at each step.

node* slower(begin), * faster(begin); //two pointers
while(faster = faster->next)
{
    if(faster == slower) { throw exception("There's a cycle"); }
    faster = faster->next;
    if(faster == slower) { throw exception("There's a cycle"); }
    slower = slower->next;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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