Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a Linked List, find out if there is a cycle in it.
Using a Hash Set to Determine Cycle in the Linked List
We can use a hash set (as a note book) to remember the nodes we have seen in the Linked List. If a node is always in the hash set, we know there is a cycle.
1 2 3 4 5 6 7 8 | def hasCycle(head): vis = set() while head is not None: if head in vis: return True vis.add(head) head = head.nextNode return False |
def hasCycle(head):
vis = set()
while head is not None:
if head in vis:
return True
vis.add(head)
head = head.nextNode
return FalseTime complexity is O(N) and space complexity is O(N) as we are using a hash set (additional space). N is the number of the nodes in the linked list.
Fast and Slow Pointer to Deterimine the Cycle in the Linked List
Given two pointers, fast and slow. Fast pointer traverses two steps at a time, and Slow pointer traverses one step at a time. If they meet somewhere, it means there is a cycle.
1 2 3 4 5 6 7 8 | def hasCycle(head): fast, slow = head, head while fast is not None and fast.nextNode is not None: fast = fast.nextNode.nextNode slow = slow.nextNode if fast == slow: return True return False |
def hasCycle(head):
fast, slow = head, head
while fast is not None and fast.nextNode is not None:
fast = fast.nextNode.nextNode
slow = slow.nextNode
if fast == slow:
return True
return FalseTime complexity is O(N) and space complexity is O(1) constant as we are using only two pointers.
–EOF (The Ultimate Computing & Technology Blog)
GD Star Rating
loading...
355 wordsloading...
Last Post: Algorithm to Find the Longest Alliteration
Next Post: Breadth First Search Algorithm to Find the Number of Lands (Land and Sea)