Linked list cycle#

Levels: level-1

Data structures: linkedlist

Practice Link#

Description#

Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to.
If pos is -1, then there is no cycle in the linked list.

Examples#

1Input: head = [3,2,0,-4], pos = 1
2Output: true
3Explanation: There is a cycle in the linked list, where tail connects to the second node.

1Input: head = [1,2], pos = 0
2Output: true
3Explanation: There is a cycle in the linked list, where tail connects to the first node.

Thinking#

This can be solved using tortoise and hare approach or using hashtable.

Python Solution#

 1class Solution(object):
 2    # Tortise and hare approach
 3    def hasCycle(self, head):
 4        try:
 5            slow = head
 6            fast = head.next
 7            while slow is not fast:
 8                slow = slow.next
 9                fast = fast.next.next
10            return True
11        except:
12            return False