L15. Find the length of the Loop in LinkedList
Вставка
- Опубліковано 27 сер 2024
- Problem Link: tinyurl.com/5n...
Entire LL Sheet: takeuforward.o...
Check our A2Z DSA Course: takeuforward.o...
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/take...
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.
Immense approach for any beginner , its crisp as well as detailed . Thanks Striver for being Striver
Solved with optimal approach without seeing the solution ❤❤🎉
i solved via brute force but couldn't think for the optimal solution sadly
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.
Yes, the same thought also comes to mind, but I don't know why it's not working.
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
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
Understood.......Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Solved By Own by watching your previous Lecture.
optimized wala ya brute force
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;
}
}
Understood,thanks striver for this amazing video.
the best tutorials
ever
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) ??
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
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;
}
}
Thank you 💟 🙃 I'm doing dsa with striver !
But sorry because I downloaded all Videos 😅
Sir really grateful to you 🙏 just one question if the heap videos will come? As not liking any other tutor after learning from you
Understood;
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😒
Understood
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;
}
Understood! but what will be the Time Complexity??
Time complexity will be O(N*length of loop) but we can consider it somewhere around O(N) and space will be O(1)
@@govindasharma9077 TC: O(N + length of loop)
O(2n)
@@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)
O(len)+O(len of loop)
Understood, thank you.
Understood✅🔥🔥
superb
Thank you so much!!
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
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).
@@priyadarsimishra7909can you give me a test case because as far i see even for the case you mentioned it seems to work fine
@@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.
@@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
awesome bro
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;
}
Can someone please explain why he wrote fast=fast.next before and inside while loop
before to move the fast to next node and next in the while loop to start the count from there!!
nice dude
understood
complexity ?
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???
Crct bro I too applied the same logic and it works
WRONG BRO
@@AkOp-bf9vm why?
@@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
understoodd
arigato
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
someone plz answer
🤔🤔
@@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
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.
US
What will be time complexity of optimal approach ?
Will it be O(2N)?
Plz answer
Can someone send brute force method 's code .
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;
}
@@vineetverma3964 Love ya bruh
us
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;
}
Understood
understood
Understood
Understood
understood