L15. Find the length of the Loop in LinkedList

[@zainabkhan-ym3kh]

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.

[@AshishSingh-he2qo]

Solved with optimal approach without seeing the solution ❤❤🎉

[@endlesslearning26]

i solved via brute force but couldn't think for the optimal solution sadly

[@KARTHIKEYANR-b1n]

I solved using brute

[@MaheshPatil-of1zy]

Solved By Own by watching your previous Lecture.

[@Benstokes4444]

optimized wala ya brute force

[@shamanthhegde]

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; } }

[@ritikshandilya7075]

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

[@stith_pragya]

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

[@_CodeLifeChronicles_]

the best tutorials ever

[@ArpitDharmshaktu]

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.

[@sandiprath4896]

Yes, the same thought also comes to mind, but I don't know why it's not working.

[@AkOp-bf9vm]

it will not work for LL 1->2->3->4->5->6->7->8->9->8 here length of Loop is 2 but slow will be more than 2. THIS CODE WILL ONLY WORK WHEN SLOW POINTER REACH STARTING NODE OF THE LOOP AND FAST POINTER SHOULD NOT PASS THE CURRENT NODE OF SLOW

[@vamsikrishnagannamaneni912]

distance from slow node to collision of nodes is infact 'd' but how will find it? After finding the starting point of cycle will you traverse the slow again till collision? This will yield same time complexity

[@hareshnayak7302]

Understood,thanks striver for this amazing video.

[@VisibleNasir]

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

[@satyamgupta-pv2ib]

cnt not go at 10:02 slow =fast node at the last , cnt start with one cnt stop at one step back where slow=fast node ......code is write But explaination is awersome Thankyou Striver

[@SouravSahu-f1y]

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

[@BadalDesai-s7h]

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]

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]

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; } }

[@YourCodeVerse]

Understood✅🔥🔥

[@NazeerBashaShaik]

Understood, thank you.

[@akshaysmart6257]

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😒

[@ManishLakkavatri]

Understood! but what will be the Time Complexity??

[@govindasharma9077]

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]

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

[@abhaymandal4903]

O(2n)

[@abhaymandal4903]

​@@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]

O(len)+O(len of loop)

[@krishkothari8634]

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; }

[@NonameNoname-f2t]

superb

[@selene8721]

Thank you so much!!

[@RajNamdev_19]

Understood;

[@ಪ್ರಯತ್ನ-ಞ3ಧ]

7:05 superbike sound 😌.... Yes guys I got distracted..

[@striverdaaadi]

awesome bro

[@TS-oj3vd]

time complexity?

[@dewanandkumar8589]

Understood

[@abhinavprabhat4418]

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; }

[@nishant4595]

was able to solve this.....

[@iamnottech8918]

complexity ?

[@priyanshuchaudhary6469]

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]

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]

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

[@priyadarsimishra7909]

@@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.

[@AkOp-bf9vm]

@@shamanthhegde it will not work for LL 1->2->3->4->5->6->7->8->9->8 here length of Loop is 2 but slow will be more than 2. THIS CODE WILL ONLY WORK WHEN SLOW POINTER REACH STARTING NODE OF THE LOOP AND FAST POINTER SHOULD NOT PASS THE CURRENT NODE OF SLOW

[@Trollvideos1154]

nice dude

[@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]

Crct bro I too applied the same logic and it works

[@AkOp-bf9vm]

WRONG BRO

[@shamanthhegde2820]

@@AkOp-bf9vm why?

[@AkOp-bf9vm]

@@shamanthhegde2820 check for the test case 1->2->3->4->5->6->7->8->9->8 HERE LENGTH OF LOOP IS 2 BUT LENGTH OF SLOW POINTER MOVES FROM START IS GREATER THAN 2

[@PixelPioneer92800]

understood

[@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!!

[@PremShinde-p4q]

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

[@shaiksoofi3741]

understoodd

[@SamyakSharma-oy1bv]

respect++;

[@rajatshukla2605]

Undestood

[@successvibes1604]

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]

someone plz answer 🤔🤔

[@GauravSharma-ij1ym]

​@@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]

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.

[@ashishpradhan6250]

arigato

[@rinokamura1152]

Can someone send brute force method 's code .

[@vineetverma3964]

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]

@@vineetverma3964 Love ya bruh

[@iamnoob7593]

US

[@cenacr007]

us

[@dayashankarlakhotia4943]

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; }

[@pradipkumarmukhi]

Understood

[@abhinanda7049]

understood

[@abhishekprasad010]

Understood

[@hardikpatel352]

understood

[@meghasharma4875]

understood

[@rutujashelke4208]

Understood

[@abhinavabhi3568]

Understood