Detect Loop in a Linked List || Program 27 || Competitive Coding || Learning Monkey ||
Detect Loop in a Linked List
In this class, we discuss Detect Loop in a Linked List.
The reader can take a complete competitive coding course. Click Here.
Question:
Given a singly linked list.
Our task is to detect a loop in a given linked list.
Example:
Input: 1-2-3-4-5-pointing to node 3
Output: Yes
The last node points to the third node.
It is forming a loop, so the output is Yes.
Example 2:
Input: 1-2-3-None
Output: No
Time complexity: O(N)
Space complexity: O(1)
Logic:
Maintain a list of all visited nodes.
Loop on the linked list, and each node visited is maintained in a list.
Suppose we visit the node already in the list. Loop exists.
If we find None in the list, there is no loop.
Second Way:
Floyd’s cycle finding algorithm.
Two objects are moving in a circle.
One object is moving slowly, and the other object is moving fast.
The faster object will move fast and meet the slower object.
We use the same concept in finding the loop.
Take two-pointers, Slow pointers and Fast pointer.
The slow pointer moves one step, and the fast pointer moves two steps.
If there is a loop in the linked list, the fast pointer will meet the slow pointer.
Then we say the loop exists in the linked list.
Code:
def detectLoop(self, head)
slow_p = head
fast_p = head
while(slow_p and fast_p and fast_p.next):
slow_p = slow_p.next
fast_p = fast_p.next.next
if slow_p == fast_p:
return True
return False
Link for playlists:
/ @learningmonkey
Link for our website: https://learningmonkey.in
Follow us on Facebook @ / learningmonkey
Follow us on Instagram @ / learningmonkey1
Follow us on Twitter @ / _learningmonkey
Mail us @ learningmonkey01@gmail.com
Auf dieser Seite können Sie das Online-Video Detect Loop in a Linked List || Program 27 || Competitive Coding || Learning Monkey || mit der Dauer stunde minuten sekunde in guter Qualität ansehen, das der Benutzer Learning Monkey 22 Februar 2023 hochgeladen hat, den Link mit Freunden und Bekannten teilen, dieses Video wurde auf Youtube bereits 58 Mal angesehen und es wurde von 3 den Zuschauern gefallen. Viel Spaß beim Betrachtenden Zuschauern gefallen!
