L15. Find the length of the Loop in LinkedList

No video

L15. Find the length of the Loop in LinkedList

Рет қаралды 41,097

8 ай бұрын

Problem Link: tinyurl.com/5n78kcda
Entire LL Sheet: takeuforward.org/linked-list/...
Check our A2Z DSA Course: takeuforward.org/strivers-a2z...
Please do give us a like, and subscribe to us if you are new to our channel.
Do follow us on our socials: linktr.ee/takeuforward

Пікірлер: 61

@zainabkhan-ym3kh 5 ай бұрын

I am addicted to go through the procedure of brute to optimize solution and sometime its frustrating when someone just mug up the solution without giving insights like you striver.

@ritikshandilya7075 3 ай бұрын

Immense approach for any beginner , its crisp as well as detailed . Thanks Striver for being Striver

@hareshnayak7302 3 ай бұрын

Understood,thanks striver for this amazing video.

@stith_pragya 2 ай бұрын

Understood.......Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

@_CodeLifeChronicles_ 2 ай бұрын

the best tutorials ever

@selene8721 3 ай бұрын

Thank you so much!!

@NazeerBashaShaik 3 ай бұрын

Understood, thank you.

@VisibleNasir 5 ай бұрын

Thank you 💟 🙃 I'm doing dsa with striver ! But sorry because I downloaded all Videos 😅

@YourCodeVerse 6 ай бұрын

Understood✅🔥🔥

@user-ke7fs7ds6h 7 ай бұрын

awesome bro

@ArpitDharmshaktu 11 күн бұрын

i think we can decrease the time cmplx. a little bit more by just taking the length from starting to the coliision node i.e (L1+d) where L1 is the distance from starting to the slow node when it reaches the junction and d is the distance of that slow node to the coliision of nodes for better understanding of how L1+d can be the length of the loop check the last video which is finding the starting point of loop.

@user-bf9hn4sw1n 3 ай бұрын

Sir really grateful to you 🙏 just one question if the heap videos will come? As not liking any other tutor after learning from you

@user-ik3qu5uy5e 5 ай бұрын

superb

@MaheshPatil-of1zy 20 күн бұрын

Solved By Own by watching your previous Lecture.

@Benstokes4444 18 күн бұрын

optimized wala ya brute force

@shamanthhegde 5 күн бұрын

Let me know pls whether you did the same or something different //Time Complexity: O(n) //Space Complexity: O(1) public class Solution { public int lengthOfCycle(ListNode head) { if(head == null || head.next == null) return 0; int count = 0; ListNode fast = head; ListNode slow = head; while(fast!=null && fast.next!=null) { fast = fast.next.next; slow = slow.next; count++; if(fast == slow) { return count; } } return 0; } }

@bharathns1361 7 ай бұрын

nice dude

@RajNamdev_19 Күн бұрын

Understood;

@PixelPioneer92800 7 ай бұрын

understood

@abhishekprasad010 2 ай бұрын

Understood

@shaiksoofi3741 Ай бұрын

understoodd

@iamnottech8918 6 ай бұрын

complexity ?

@user-ff4ny5pm9m 5 ай бұрын

Hey Striver just wondering, In the last video about finding the loop starting point you said that the loop length will be "L1 + d" so can't we just return the number of steps slow moved before we detect the loop (fast==slow) ??

@pravinthakur7791 4 ай бұрын

int lengthOfLoop(Node *head) { // Write your code here Node* slow = head; Node* fast = head; while(fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if(slow == fast) { coutnext; } cout

@shamanthhegde 5 күн бұрын

We can simplify it actually Just do the old approach of detect cycle... and whenever the fast and slow meets...the distance travelled by the slow pointer becomes the size of the loop //Time Complexity: O(n) //Space Complexity: O(1) public class Solution { public int lengthOfCycle(ListNode head) { if(head == null || head.next == null) return 0; int count = 0; ListNode fast = head; ListNode slow = head; while(fast!=null && fast.next!=null) { fast = fast.next.next; slow = slow.next; count++; if(fast == slow) { return count; } } return 0; } }

@ManishLakkavatri 7 ай бұрын

Understood! but what will be the Time Complexity??

@govindasharma9077 7 ай бұрын

Time complexity will be O(N*length of loop) but we can consider it somewhere around O(N) and space will be O(1)

@IITians 7 ай бұрын

@@govindasharma9077 TC: O(N + length of loop)

@abhaymandal4903 6 ай бұрын

O(2n)

@abhaymandal4903 6 ай бұрын

@@govindasharma9077 it will not (n*length of loop ) as for every value of n there is not seperate loop. There is linear relation . So it will be O(2n)

@2amCoder 5 ай бұрын

O(len)+O(len of loop)

@ashishpradhan6250 Ай бұрын

arigato

@akshaysmart6257 2 күн бұрын

So far After watching these 15 lectures on LinkedList why I feel more confident in LinkedList than Arrays😅😅?? Is the linkedlist concept itself easy or I didn't concentrate more on Arrays. I even completed the Arrays playlist 2 times😒

@utkarshiitbhu4204 Ай бұрын

but when they collide suppose from starting of loop their length is d and the remaining is L1 which is length from starting link list to starting loop so loop is L1+D whish is the amount slow pointer covers???

@shamanthhegde2820 5 күн бұрын

Crct bro I too applied the same logic and it works

@AK-wc1cv Ай бұрын

Can someone please explain why he wrote fast=fast.next before and inside while loop

@madhu_mohanreddy Ай бұрын

before to move the fast to next node and next in the while loop to start the count from there!!

@priyanshuchaudhary6469 2 ай бұрын

i have a question,in your last videos you have taught us that the total distance of loop will be d+L1 where L1 will be the same distance from the head to that node which is the starting node of the loop and d is the distance from the starting node of the loop where slow was present and when slow pointer meets with fast pointer in the clockwise direction. So why can't we only calculate the total distance from starting to the node where slow pointer meets the fast pointer int count=0; Node slow=head,fast=head; while(fast!=null && fast.next!==null) { slow=slow.next; fast=fast.next.next; count++; if(slow==fast) { return count; } } i have just written main code Someone plz explain

@priyadarsimishra7909 2 ай бұрын

You need to account for one edge case where the length of the loop is not necessarily always L1 + d. This is because L1 could be large and the loop could be small. The initial L1 distance is always divisible to the length of the loop (you can just draw some cases out and see this).

@shamanthhegde 5 күн бұрын

@@priyadarsimishra7909can you give me a test case because as far i see even for the case you mentioned it seems to work fine

@priyadarsimishra7909 5 күн бұрын

@@shamanthhegde I am saying that it is not always L1 + d because the length of the loop could be only 2 or 3 nodes whereas L1 is like 5 nodes, so in that case you just loop till fast reaches itself again. That would be the loop length else if fast reaches slow then we have the loop length as well.

@abhinavprabhat4418 7 ай бұрын

int lengthOfLoop(Node *head) { Node* fast = head; Node* slow = head; int cnt = 0; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) { do { cnt++; fast = fast->next; } while (slow != fast); return cnt; } } return 0; }

@iamnoob7593 5 ай бұрын

@user-xp3hf2mb2u 4 ай бұрын

What will be time complexity of optimal approach ? Will it be O(2N)? Plz answer

@krishkothari8634 2 ай бұрын

int lengthOfLoop(Node *head) { // Write your code here Node* slow = head; Node* fast = head; while(fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if(slow == fast) { int cnt = 0; do { fast = fast->next; cnt++; } while(fast != slow); return cnt; } } return 0; }

@rinokamura1152 6 ай бұрын

Can someone send brute force method 's code .

@vineetverma3964 6 ай бұрын

int findLoopLength(ListNode* head) { std::unordered_map nodeMap; // Map to store node addresses and their corresponding indices ListNode* current = head; int index = 0; while (current != nullptr) { // Check if the current node is already in the map if (nodeMap.find(current) != nodeMap.end()) { // Loop detected, calculate the length int loopStartIndex = nodeMap[current]; return index - loopStartIndex; } // Add the current node to the map nodeMap[current] = index; // Move to the next node current = current->next; index++; } // No loop found return 0; }

@rinokamura1152 6 ай бұрын

@@vineetverma3964 Love ya bruh

@successvibes1604 7 ай бұрын

int lengthOfLoop(Node *head) { Node* slow = head; Node* fast = head; while(fast!=NULL and fast->next!=NULL){ fast = fast->next->next; slow = slow->next; if(fast == slow){ int ct = 1; slow = head; //slow = slow->next; while(slow != fast){ slow = slow->next; ct++; } return ct; } } return NULL; why this code is not working as distance from head to the point where fast and slow collide show be equal to the length of loop because in last lec where we calculated the starting point of loop we have used this concept slow = head than move till fast collide with slow someone plz explain

@successvibes1604 7 ай бұрын

someone plz answer 🤔🤔

@GauravSharma-ij1ym 6 ай бұрын

@@successvibes1604 just take a Linked List with just 3 elements in loop and atleast 8 elements in linear chain before loop . Dry run it and u will get your amswer

@aarzookhunger9487 4 ай бұрын

it shouldn't be calculated from slow = head *after you initialised the ct* instead do slow = slow->next as in the loop that we've detected , it will move slow one step ahead than fast and calculate the length of loop until we again hit fast. Else the code looks correct.

@cenacr007 3 ай бұрын

@dayashankarlakhotia4943 8 ай бұрын

public int countNodeInloop{ Node head){ Node fast =head,slow=head; int cnt=1; while(fast.next!=null&&fast.next.next!=null){ slow=slow.next; fast=fast.next.next; if(slow==fast){ fast=fast.next; while(slow!=fast){ cnt++; fast =fast.next; } return cnt; } } return 0; }