L6. Odd Even Linked List | Multiple Approaches
Problem Link: tinyurl.com/47fu86tm
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
Пікірлер: 200
Great video just a small correction that it will be even = even.next Here's the full code for leetcode: ListNode* oddEvenList(ListNode* head) { if(head == NULL || head->next == NULL) return head; ListNode* odd = head; ListNode* even = head->next; ListNode* evenHead = head->next; while(even!=NULL && even->next!=NULL){ odd->next = odd->next->next; even->next = even->next->next; odd = odd->next; even = even->next; } odd->next = evenHead; return head; }
@NotNewton23
6 ай бұрын
just figured out and then found your comment 😅😅
@parvahuja7618
6 ай бұрын
i was wondering the same
@_PRANAYMATE
5 ай бұрын
Good job Bro
@shaikkhizar8133
5 ай бұрын
Yes I agree with you
@imamansoni
4 ай бұрын
Typo ke vajah se 2 baar video dekh liya mai 😂
if anyone is facing any issue with the while condition ie, while(even != NULL && even -> next != NULL) you can use instead, while(odd -> next != NULL && even -> next != NULL) i hope it helps you , happy coding.
@aayushraj7290
3 ай бұрын
can u explain why cant I keep condition as while(even.next !=null), why to check if even is null or not..
@harshit.53
2 ай бұрын
@@aayushraj7290 take an odd length LL and do the dry run of the code, you will understand why you need to check if even != NULL
@guttulavybhav1030
18 күн бұрын
bro odd .next is nothing but even
Raj bhai hats off to your dedication
hey guys, in the optimal solution, inside while loop, we have already set the next for both even and odd, so to go next even and odd use even= even->next ; odd= odd->next respectively I spend my 20-30 minutes realising this lol :)
All the video lectures and the articles helped me a lot to gain confidence in DSA and will be helping me in the interviews. Thank you Striver bhaiya for bringing such amazing content for free.
@touchskyfacts1391
4 ай бұрын
Hlo bro ?? Have you given any interview yet? What are you currently doing?
@AmanSharma-xy1qm
4 ай бұрын
@@touchskyfacts1391 Yes i gave approx 7 interview and got selected in 3 of them, in one they were offering me QA engineer role due to different tech stacks so i denied, in 2 of them i choose the 2nd which was 4.5 LPA. In the beginning i wasn't good at DSA so i got rejected then i started Striver A to Z and learned String, Array, Matrix, LinkedList, Stacks, Queue and basic of advance DS. that was enough to get this.
i can surely say that this is the best linkedList course of all time
Thanks for making our concepts clear Striver
Amazing explanation. Loved it.
I solved this with the optimal approch without looking at sol for the first time, thanks Striver for teaching all the intutions and logical process everytime
@faique509
6 күн бұрын
was going to comment the same..i think we should do the dsa together..if you are interested let me know..or u can drop your insta..
understood.. guru jee... thanks to my senior who suggested me to go through your videos
Understood... Superb bhaiya ❤
love the way you teach
one mistake even = even->next instead of even=even->next->next
@sanskarsawant6936
8 ай бұрын
i was finding where this even.next.next is coming.... thanks for confirming
@ritochitghosh1753
3 ай бұрын
@@sanskarsawant6936 Same
@THOSHI-cn6hg
9 күн бұрын
exactly
i dont know even a single thing about dsa, this is bcz of striver i got an amazing job, hats off to u
Understood.Thanks for the wonderful lecture.
Thanks Striver!!!
I liked it first thnaks for the course you are the best
Awesome❤ explanation guru...
just love your explaination
solved without watching, kudos to previous videos base creation !!
We would need to check if head !=null before initializing even as head.next and while updating even , even.next should be good enough , even.next.next would land us on an odd node.
Undestood, thank you!
Thanks a lot striver, understood
Understood thankyou so much striver
line even = even.next.next; inside the while loop. When updating the even pointer, you should check if even.next is not null before trying to access even.next.next. Small correction to be made
great video bhaiya
The great wall of dsa😍😍
lecture 6 done,love u bhaiya
Lovely Explanation
Understood bhaiya 🔥
Understood, thank you.
great explanation
Thanks bhaiya...❤🎉
0(n)time complexity, understood thank you striver bhaiya
@succesmantramotivational8795
5 ай бұрын
yesss
UNDERSTOOD CLEARLY
i think even next should also be even.next rather than even.next.next
@souradeepchowdhury667
8 ай бұрын
yes, i think by mistake it is written
@tanay776
8 ай бұрын
you are right
@muwaffaqelbadawi
8 ай бұрын
You're absolutely correct!
@ravijha377
8 ай бұрын
No it will be even->next->next only
@Raj-iw9hd
7 ай бұрын
@@ravijha377 can you explain why ?
Thanks A lot Bhaiya
I got it but you should have done a dry run o an odd LL also. but no prob i did that by my self. great explanation bro.
Understood , Thank youu
O(n/2) space complexity. i was wrong. it'll be O(n) because we need to consider the operations taking place twice inside the array
Thanx bro
Nice one! :)
Understood✅🔥🔥
Why is the time complexity O(n/2) * 2? It should be O(n/2) regardless of the number of operations performed inside the loop, right?
Striver on 🔥
Understood Sir
Thanks
Thanku bhaiya
understood 👍
Dude I had solved this que using convert LL into array and performed operation on array and at the end create new LL and return it.
Here is the java program class Solution { public ListNode oddEvenList(ListNode head) { //edge case if(head==null || head.next==null) return head; ListNode odd=head; ListNode even=head.next; ListNode evenHead=head.next; while(even !=null && even.next!=null){ odd.next=odd.next.next; even.next=even.next.next; odd=odd.next; even=even.next; } odd.next=evenHead; return head; } }
Understood 🎉
Understood! sir
understood❤
Time complexity O(n/2) because the while loop will run max of n/2 times.
Understood
understood!
Understood!
Understood.
UNDERSTOOD
Understood..!!
Understood !!
we need the article for rest of the linked list problems of A2Z sheet
understood
What sincerity Striver. Respect Man
Time complexity : O(N) -> because we're traversing the whole LL Space Complexity : O(1) -> we're not using any auxillary space for solving the problem.
Time Complexity O(N/2)
understood:))
can also be done using dummyNode method : ListNode* oddEvenList(ListNode* head) { if(head==NULL||head->next==NULL){ return head; } ListNode *temp=head; ListNode *dummyListNode=new ListNode(0); ListNode *evenTemp=dummyListNode; ListNode *prev=NULL; int count=1; while(temp!=NULL){ if(count&1){ prev=temp; temp=temp->next; }else{ prev->next=temp->next; temp->next=NULL; evenTemp->next=temp; evenTemp=evenTemp->next; temp=prev->next; } count++; } prev->next=dummyListNode->next; return head; }
Time Complexity = O(N) As we are traversing through odd and even Nodes. Though it seems O(N/2) but in every loop we are traversing twice(for odd and for even indexed nodes), so Time Complexity will be O(N) I think. If I am wrong please point it out.
Next series on strings or cp
actually there is prblem oocuring after writing evehead=head.next still it can t connect it to the even with last index of odd
in pseudo code of optimal approach , it should be even=even.next instead of even=even.next.next in while loop.
Time Complexity - O(n/2)
We can also include another case if its only 2 element Linked List then also we do nothing
understod
time complexity O 2(n/2) space O(1)
Time Complexity=O(N/2) Space Complexity=O(1) Thankyou for your Lecture
he knows where everyone make mistakes like o(n/2)
Understood;
Understood as fast as O(1)
Also, without edge case we get runtime error: if(head == null || head.next == null) return head;
Ahh, i was using 2 while loops for odd and even so it was giving TLE.
LC 328. // Naive solution class Solution { public: ListNode* oddEvenList(ListNode* head) { // naive solution is using a list to store the data vector arr; ListNode* temp = head; if(head ==NULL || head->next == NULL ) return head; while(temp!=NULL && temp->next!=NULL){ arr.push_back(temp->val); temp = temp->next->next; } if(temp) arr.push_back(temp->val); temp = head->next; while(temp!=NULL && temp->next!=NULL){ arr.push_back(temp->val); temp = temp->next->next; } if(temp) arr.push_back(temp->val); int i =0; temp = head; while(temp!=NULL){ temp->val = arr[i]; i++; temp = temp->next; } return head; } }; // optimised solution class Solution { public: ListNode* oddEvenList(ListNode* head) { if(head == NULL || head->next == NULL ) return head; ListNode* oddptr = head; ListNode* evenptr = head->next; ListNode* evenhead = head->next; while(evenptr !=NULL && evenptr->next!=NULL){ oddptr->next = oddptr->next->next; evenptr->next = evenptr->next->next; oddptr = oddptr->next; evenptr= evenptr->next; } oddptr->next = evenhead; return head; } };
Why did the brute force seemed more complex than the optimized 💀
Why do we need evenhead? Why can’t we make last odd point to head.next which will logically be first even position?
TC = O(N)........... SC= O(1)
UnderStood
👍🏻👍🏻
this is the java code * * class Solution { public ListNode oddEvenList(ListNode head) { if(head==null ||head.next==null){ return head; } ListNode odd=head; ListNode even=head.next; ListNode connector=head.next; while(even!=null && even.next!=null){ odd.next=odd.next.next; even.next=even.next.next; odd=odd.next; even=even.next; } odd.next=connector; return head; }
Striver, is it even possible to run 2 separate loops? Because after running the first loop, the oddHead's next.next is not pointing to the next odd, but its pointing to the next even node (already altered in the first loop).
@anuragprasad6116
5 ай бұрын
no not possible
O(N/2) time complexcity
Understood, but one small doubt ,why didn't we consider the operations in the while loop as unit operations?
@shreyxnsh.14
6 ай бұрын
unit =1 and they are two operations
@shreyxnsh.14
6 ай бұрын
also you can see that you are traversing through every single element.
This approach won't work if your linked list has an odd number of nodes.
@ganjinaveen7338
8 ай бұрын
it works for any number of nodes check out this if not head or not head.next: return head odd=head even=head.next evenhead=head.next while even and even.next: odd.next=odd.next.next even.next=even.next.next odd=odd.next even=even.next odd.next=evenhead return head
@psionl0
7 ай бұрын
@@ganjinaveen7338 I see.
@dikshasoni52a98
5 ай бұрын
U just need to add some if case and it will work even for odd case..
@voicegovindpur108
Ай бұрын
It will work for odd as well even case because it there are odd even->next will terminate the loop and you can link the evenHead to odd
why it's not working for using 2 loops separately for even and odd nodes.I wrote this ListNode* odd = head; ListNode* even = head->next; ListNode* evenhead = even; while(odd!=NULL && odd->next!=NULL && odd->next->next!=NULL) { odd->next = odd->next->next; odd = odd->next; } while(even!=NULL && even->next!=NULL && even->next->next!=NULL) { even->next = even->next->next; even = even->next; } odd->next = evenhead; return head;
"UNDERSTOOD"
Correct solution that beats 100%: class Solution { public: ListNode* oddEvenList(ListNode* head) { if(head==NULL || head->next==NULL) return head; ListNode* odd = head; ListNode* even = head->next; ListNode* evenHead = head->next; while(even!=NULL && even->next != NULL){ odd->next = odd->next->next; even->next = even->next->next; odd = odd->next; even = even->next; } odd->next = evenHead; return head; } }; Time complexity will be O(N) as we are traversing through each and every element
Small correction it will be even =even->next; not even->next->next;
can we do while(temp.next != null && temp.next.next != null){ temp = temp.next.next; } Like hare as it was also taking 2 jumps
while(even!=NULL && even->next!=NULL){ odd->next = odd->next->next; even->next = even->next->next; // line 3 odd = odd->next; even = even->next; } try this if you also face runtime error WHY? even = even -> next because we already assigned even->next->next to even->next at line 3