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

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.)

NOTE: please submit atleast any three (3) test cases. (C++)

Explanation / Answer

a) O(N) space, O(N) time

Use Hashing:
Traverse the list one by one and keep putting the node addresses in a Hash Table. At any point, if NULL is reached then return false and if next of current node points to any of the previously stored nodes in Hash then return true.

b)   O(1) space, O(N) time

This is the fastest method. Traverse linked list using two pointers. Move one pointer by one and other pointer by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.

#include <iostream>
#include <cstdlib>
using namespace std;

/* Link list node */
struct node
{
int data;
struct node* next;
};

void push(node** head_ref, int new_data)
{
/* allocate node */
node* new_node = new node;

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

bool detectloop(node *list)
{
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 == fast_p)
{
cout<<"Found Loop"<<endl;;
return true;
}
}
return false;
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
node* head = NULL;

push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);

/* Create a loop for testing */
head->next->next->next->next = head;
detectloop(head);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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