1.

Write functional code for solving the problem given below: Detect whether or not a given linked list contains a cycle.

Answer»

C ++ function which solves the given Data STRUCTURES and Algorithm problem is given below:

bool detectCycle(ListNode* root){ ListNode *slow = root, *fast = root; while (slow && fast && fast -> link) { slow = slow->link; fast = fast->link->link; if (slow == fast) { return true; } } return false;}

For solving this question, we can use Floyd's Approach to Find cycle in a linked list. It is stated below:

  • Two POINTERS are used for TRAVERSING the linked list.
  • One pointer (slow) should be moved by one, while another pointer (fast) should be moved by two.
  • There is a loop if these points intersect at the same node. A linked list does not have a loop if the pointers do not MEET.


Discussion

No Comment Found

Related InterviewSolutions