L6. Odd Even Linked List | Multiple Approaches

[@Tanveermd7]

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]

can u explain why cant I keep condition as while(even.next !=null), why to check if even is null or not..

[@harshit.53]

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

bro odd .next is nothing but even

[@nachikettiwary5628]

@@guttulavybhav1030 no bro, odd.next is odd.next.next . So when you do odd.next , it will go to the next odd place. Hope it helps

[@Mrindia-k8n]

na man it's wrong sorry but the first one is correct and the perfect one well u can do one thing if u can say odd.next==evenhead if u include this condition with the first one it will be more accurate

[@edisane8763]

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]

just figured out and then found your comment 😅😅

[@parvahuja7618]

i was wondering the same

[@_PRANAYMATE]

Good job Bro

[@shaikkhizar8133]

Yes I agree with you

[@imamansoni]

Typo ke vajah se 2 baar video dekh liya mai 😂

[@amangoyal8341]

i can surely say that this is the best linkedList course of all time

[@champ-kx9lb]

well explained! There is slight error in the brute force code that in while loop at the last line in loop even=even.next; so if anyone find its confusing can be helped from this.

[@manishmahajan6094]

Marking my Day 21 of learning DSA. Thanks for the great course with clear in-depth explanation

[@AmanSharma-xy1qm]

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]

Hlo bro ?? Have you given any interview yet? What are you currently doing?

[@AmanSharma-xy1qm]

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

[@sourabhtiwari5137]

i dont know even a single thing about dsa, this is bcz of striver i got an amazing job, hats off to u

[@ashmitshelke1444]

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]

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

[@retromania526]

​@@faique509i cant build logic its tough to remember approaches

[@CodeNinja18]

one mistake even = even->next instead of even=even->next->next

[@sanskarsawant6936]

i was finding where this even.next.next is coming.... thanks for confirming

[@ritochitghosh1753]

@@sanskarsawant6936 Same

[@THOSHI-cn6hg]

exactly

[@user-zv4cr5xd1g]

ty

[@bhavyasharma3500]

Raj bhai hats off to your dedication

[@pushankarmakar1783]

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

[@__PiyushMittal]

Understood Bhaiya , And i still watching all of your videos till the End.

[@nitishkumarram8978]

0(n)time complexity, understood thank you striver bhaiya

[@succesmantramotivational8795]

yesss

[@shashamnk2525]

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.

[@NotNewton23]

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 :)

[@GODLUCIFER-m8d]

still i cant understand. could u help me to clear this i used chatbot and some stuffs still no use, i think my brain is twisted to understand this concept

[@rumiNITPatna]

could u pls explain this.

[@NotNewton23]

Sorry guys, I am not into coding field anymore and currently into other domain.

[@rumiNITPatna]

@@NotNewton23 👍👍

[@BharathMurugan30]

@@rumiNITPatna Since we perform the operation odd->next = odd->next->next , odd->next is already linked to the next odd place. So, if we want to move odd to the next position, it is odd->next, because odd->next is currently pointing to odd->next->next. If you still didn't understand, you can draw a linkedlist of four elements and try linking the elements with this operation

[@ritikshandilya7075]

Thanks for making our concepts clear Striver

[@prathameshjadhav2942]

Understood... Superb bhaiya ❤

[@saketjaiswal3431]

understood.. guru jee... thanks to my senior who suggested me to go through your videos

[@ketonesgaming1121]

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

[@chetandatta9051]

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?

[@harshitjaiswal9439]

Amazing explanation. Loved it.

[@BhavyaJain-qz8jg]

solved without watching, kudos to previous videos base creation !!

[@zainiqbal7990]

What sincerity Striver. Respect Man

[@snehashisratna9074]

love the way you teach

[@rajmohitkumar3644]

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

[@striverdaaadi]

The great wall of dsa😍😍

[@veedofficial]

I liked it first thnaks for the course you are the best

[@Vvvvviieiei123]

lecture 6 done,love u bhaiya

[@vaibhavgupta0901]

Understood thankyou so much striver

[@samarthpai5359]

The time complexity of the optimal solution is O(N/2) and space complexity is O(1) Edit: it was O(N)

[@patilrajesh2500]

Lecture successfully completed on 27/11/2024 🔥🔥

[@nandeesh_2005]

Awesome❤ explanation guru...

[@vishakhajoshi277]

Good explanation! Thanks :)

[@PradipKumar-zi2pz]

We can have this approach as well. def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]: if head is None or head.next is None or head.next.next is None: return head odd = head even = head.next while even and even.next: temp = even.next.next oddnext = odd.next odd.next = even.next odd = even.next odd.next = oddnext even.next = temp even = temp return head

[@lovetiwadiai9909]

i think even next should also be even.next rather than even.next.next

[@souradeepchowdhury667]

yes, i think by mistake it is written

[@tanay776]

you are right

[@muwaffaqelbadawi]

You're absolutely correct!

[@ravijha377]

No it will be even->next->next only

[@Raj-iw9hd]

@@ravijha377 can you explain why ?

[@shaikkhizar8133]

Time Complexity=O(N/2) Space Complexity=O(1) Thankyou for your Lecture

[@diptanjankar9848]

Striver on 🔥

[@ishanchakraborty69]

just love your explaination

[@saravanansubbiah164]

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.

[@adebisisheriff159]

Thanks Striver!!!

[@Tanveermd7]

we need the article for rest of the linked list problems of A2Z sheet

[@rushidesai2836]

Time complexity O(n/2) because the while loop will run max of n/2 times.

[@toushikbanik8452]

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.

[@aronkumar-v8i]

time complexity O 2(n/2) space O(1)

[@oyeshxrme]

great video bhaiya

[@nptel1punith929]

Understood bhaiya 🔥

[@hardikpatel352]

Thanks a lot striver, understood

[@mhdvlogs2130]

inside the while loop instead of even=even.next.next; it will be even=even.next; bcz we r setting/updating next even node so that next time loop run then we can connect this node next to the upcoming even node, that is (even.next=even.next.next;) thnk you ~~Mhd

[@arnabkundu1648]

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.

[@jd1901-s]

OP explanation💯👌

[@rajkumarvb5197]

Undestood, thank you!

[@adityalingwal6029]

Lovely Explanation

[@shreyxnsh.14]

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

[@rishabhbajpai648]

UNDERSTOOD CLEARLY

[@bhashasinha5839]

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

[@nishigandhagirishdandekar1131]

I think it will be O(n) because we are traversing all the elements for even and odd.

[@Harsh-jc2bz]

did it by myself Java: class Solution { public ListNode oddEvenList(ListNode head) { if(head==null)return head; ListNode odd=head; ListNode even=head.next,temp=even; while(temp!=null){ if(odd.next.next==null)break; odd.next=odd.next.next; odd=odd.next; temp.next=temp.next.next; temp=temp.next; } odd.next=even; return head; } }

[@ankushladani496]

Thanks bhaiya...❤🎉

[@akshathlm7849]

Time Complexity O(N/2)

[@Mighty_kaaju]

great explanation

[@yashendrabadal4776]

Peak Content !

[@arthonuy7211]

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

[@SurajKumar-ku1lg]

he knows where everyone make mistakes like o(n/2)

[@MultiFacebookers]

Why do we need evenhead? Why can’t we make last odd point to head.next which will logically be first even position?

[@LAVLESHSINGH-s1r]

actually there is prblem oocuring after writing evehead=head.next still it can t connect it to the even with last index of odd

[@abhinavprabhat4418]

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

[@PradipKumar-zi2pz]

During DSA interview, can we use pen and paper to make approach? or will interviewer allow to use pen and paper ?

[@viveksoni6823]

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;

[@YourCodeVerse]

Understood✅🔥🔥

[@nishant4595]

was able to solve by optimal meself!

[@stevie_wanders]

What is the digital whiteboard that you use?

[@abudanish196]

💯CORRECTION:💯 even=even->next instead of even=even->next->next

[@rohanlambar4725]

Time Complexity - O(n/2)

[@nileshdesai5218]

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.

[@vedikamishra009]

that uses extra space

[@k.manasaxi-c4622]

if getting a runtime error , try out this : class Solution { public: ListNode* oddEvenList(ListNode* head) { if(head==NULL || head->next==NULL){ return head; } ListNode* odd=head; ListNode* even=head->next; ListNode* evenHead=even; while(even!=NULL && even->next!=NULL){ odd->next=even->next; odd=odd->next; even->next=odd->next; even=even->next; } odd->next=evenHead; return head; } };

[@sunayanabhowmik9690]

Also, without edge case we get runtime error: if(head == null || head.next == null) return head;

[@harshitkhandelwal2661]

We can also include another case if its only 2 element Linked List then also we do nothing

[@Harsh-jc2bz]

class Solution { public ListNode oddEvenList(ListNode head) { if(head==null)return head; ListNode odd=head; ListNode even=head.next,temp=even; while(temp!=null){ if(odd.next.next==null)break; odd.next=odd.next.next; odd=odd.next; temp.next=temp.next.next; temp=temp.next; } odd.next=even; return head; } }

[@santhoshl-zq1op]

thanks for this video

[@056_harshitagarwal8]

where can I get java code Solution for this problem....it's not in description

[@pankajsunal9819]

Understood.Thanks for the wonderful lecture.

[@s_savarnaya]

i have a doubt the odd = odd->next->next instead of odd=odd->next

[@ManishLakkavatri]

Understood, but one small doubt ,why didn't we consider the operations in the while loop as unit operations?

[@shreyxnsh.14]

unit =1 and they are two operations

[@shreyxnsh.14]

also you can see that you are traversing through every single element.

[@neerajmalhotra8277]

What software you are using for drawing?

[@NazeerBashaShaik]

Understood, thank you.

[@vidhiarora4995]

hey striver....what if the last node is an odd one? how will it justify that the odd is dependent on even?

[@arjunk04]

In this case even going to be null which is taken care by the condition specified in while loop

[@jogeshsoni2205]

in pseudo code of optimal approach , it should be even=even.next instead of even=even.next.next in while loop.

[@ksnayeem2743]

after linked why we write odd = odd.next but in even = even.next.next?

[@square-kstudios9561]

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]

no not possible

[@hulkstar0808]

Understood , Thank youu

[@Aditya_6996]

why not connect odd list with even list using "odd->next=head->next" instead of "odd->next=evenHead" ? I mean what would logically go wrong ?

[@vipinms4864]

the link would already been updated. so odd->next would give you the third node instead of 2nd node

[@Aditya_6996]

​@@vipinms4864 yeah understood that already but thanks

[@DeepakPatel-d5v]

Thanks A lot Bhaiya

[@hardikpatel352]

TC = O(N)........... SC= O(1)

[@fitnessforlifetamil3936]

Understood 🎉

[@shubhamrathod9249]

11:36

[@ANNAM-dv5dy]

somene explain me my doubt ? odd->next = odd->next->next; even->next = even->next->next; odd = odd->next; even = even->next; here in this first 2 lines of code , odd pointer moves to odd places and even pointer moves to even places so that even connects to even and odd connects to odd , but in the next two lines odd pointer moves to one step ahead and also even pointer moves to one step ahead i.e odd moves to even and even moves to odd ...?

[@pavanilakshmiaishwarya8962]

Yeah it is wrong in the video. It has to be: odd->next = odd->next->next even->next = odd->next->next odd = odd->next even = even->next

[@TON-108]

How can we do this using two while loops, one for even and one for odd?? I'm getting Runtime error!!

[@pravinthakur7791]

Node* segregateEvenOdd(Node* head) { // Write your code here if(head == nullptr || head->next == nullptr) return head; stackst; Node* temp = head; Node* prev = nullptr; Node* firstOddNode = nullptr; if((temp->data & 1) == 0) st.push(temp); while(temp != nullptr) { if((temp->data & 1) == 0 && prev != nullptr) { st.push(temp); while(temp->next != nullptr && (temp->next->data & 1) == 0) { st.push(temp->next); temp = temp->next; } prev->next = temp->next; } if((temp->data&1) && firstOddNode == nullptr) firstOddNode = temp; prev = temp; temp = temp->next; } Node* lastEvenNode = nullptr; Node* newHead = nullptr; while(!st.empty()) { if (newHead == nullptr) { newHead = st.top(); lastEvenNode = st.top(); } else { st.top()->next = newHead; newHead = st.top(); } st.pop(); } lastEvenNode->next = firstOddNode; return newHead; }

[@moksh7130]

Understood sir! :D

[@thisisRandom-ut9iq]

Java code public ListNode oddEvenList(ListNode head) { if(head == null || head.next == null){ return head; } ListNode first = head; ListNode second = head.next; ListNode secondHead = second; while(second != null && second.next != null){ first.next = first.next.next; first = first.next; second.next = second.next.next; second = second.next; } first.next = secondHead ; return head; }

[@DhanushS-we6ql]

small coreetcion while even node is pointing to even = even->next;