A linked list is said to contain a cycle if any node is visited more than once while traversing the list. Given a pointer to the head of a linked list, determine if it contains a cycle. If it does, return 1. Otherwise, return 0.
head refers to the list of nodes 1 -> 2 -> 3 -> NULL
The numbers shown are the node numbers, not their data values. There is no cycle in this list so return .
head refers to the list of nodes 1 -> 2 -> 3 -> 1 -> NULL
There is a cycle where node 3 points back to node 1, so return 1.
Complete the has_cycle function in the editor below.
It has the following parameter:
- SinglyLinkedListNode pointer head: a reference to the head of the list
- int: 1 if there is a cycle or 0 if there is not
Note: If the list is empty, head will be null.
References to each of the following linked lists are passed as arguments to your function:
- The first list has no cycle, so return 0.
- The second list has a cycle, so return 1.
This problem is easier to solve than it seems. The fastest way I found to solve is to have two pointers checking against each other, only that one is faster than the other, this way, if there is a cycle, the slowest one will inevitably meet the fastest, which will be trapped in the cycle.
Let’s see how this would run in the second sample input:
First, both pointers will be head, but then one will accelerate by one, pointing to its next.next:
slow = 1 -> slow = 2 -> slow = 3
fast = 1 -> fast = 3 -> fast = 3
I tried to write the solution using JS, but Hackerrank had a bug, so I had to use Python instead:
def has_cycle(head): slow = head fast = head while (fast is not None and fast.next is not None): slow = slow.next fast = fast.next.next if slow == fast: return 1 return 0