Partition List - Linked List - Leetcode 86

Подписаться 748 тыс.

Просмотров 29 тыс.

50% 1

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: leetcode.com/problems/partiti...
0:00 - Read the problem
1:20 - Drawing Explanation
4:45 - Coding Explanation
leetcode 86
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#partition #list #python

Наука

Опубликовано:

9 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 50

@nchou646 2 года назад

How did u make this question that easy??? Crystal clear explanation

@ladydimitrescu1155 Год назад

I was trying to manipulate the pointers in the list and found it sooooo convoluted, you made the problem look like it was an easy level linked list question

@raghavendrac4710 Год назад

your explanations are always the best, i view the algorithm and understand it well enough to implement myself

@najmuzzamakhan835 Год назад

Those who are saying that Space complexity here is O(N).Try to look into his code. If he would be using O(N) space, then he would be making new node for every iteration of while loop. but in reality he has only made 2 node which are dummy node (left,right) so overall space complexity is Constant O(1).

@mehulgoyal5-yeariddcivilen832 10 месяцев назад

but the memory that the code takes is same i just solved it in leetcode with a created new node in while loop and with the neetcode solution ,there is zero difference in both time and space complexity

@jatinpandey6453 5 месяцев назад

bro what are you talking about like im not even seeing code, you are literally inserting the whole input (of length n) in those two pointer and merging them !! you are not even return head(of og LL) you are returning a whole new pointer of input length n. Just letme know if im wrong!

@chrischika7026 2 месяца назад

@@jatinpandey6453 you are wrong!, all of you are wrong!

@jatinpandey6453 2 месяца назад

@@chrischika7026 i don't mind being wrong, but i do mind not knowing reason and learning why i am wrong

@nishorgohassan7328 2 месяца назад

@@jatinpandey6453 If you carefully look at it, the whole input list is just being reassigned to a new variable, no new list has been created.

@devjeff3192 3 года назад

Thank you so much, your explanation is pretty simple and easy to understand. I subscribed your channel!!! Keep it up !!!

@nandanimadhukar 3 года назад

Great videos. I really wanted someone who codes in python on youtube leetcode videos and I found you!

@cama708 2 года назад

This was so well explained thanks!!

@licokr 3 месяца назад

I don't get tired of saying it's amazing. I made previous node, left node and dummy(head) node. Basically, in my first approach, I dealt with one direction way. Coming up with conditions to make it work was not easy work but wow... Just divided into two LinkedIn lists and... it's great, and explanation easy to understand. Thanks a lot. I genuinely respect your work.

@sahejhira1346 3 месяца назад

same!

@maribelmendez-zuniga3448 13 дней назад

Very helpful video. Super thanks! 😀

@AbhishekSharma-me 10 месяцев назад

Such a great explanation.

@hillarioushollywood4267 Год назад

To whom who think that the above code uses extra space: An important thing to note here is that he showed the original linked list intact in the above diagrams. However, in the implementation, we remove the nodes from the original linked list and attach them in the before or after list. We don't utilize any additional space. We simply move the nodes from the original list around.

@hillarioushollywood4267 Год назад

If you guys add new ListNode class with currentNode value, then the space complixity will be O(N), but we are moving node to new nodeClass.

@varunshrivastava2706 Год назад

I am still confused since we are only moving head ahead and adding any particular node to a left or right where the hell are we deleting the connections from original list. For Ex - when head is at 1 we did ltail.next = head, similarly for rtail.next = head. Then left and right would look like this left -> 1 -> 4 -> 3 -> ..... and 4 - > 3 -> 2 - > ..... respectively.

@ritviklashkari 10 месяцев назад

If you're updating the tail variables each time in the loop, how does the "left" dummy node get updated? Like I don't understand how you just returned "left.next" without doing anything to "left" in the while loop.

@NEO-wl9ox 7 месяцев назад

The way you fraternizing around with your visualization notes is so immaculate , like the draws are so well organized, Is it just good practice or do you just use hand instead of mouse

@mtr2936 2 года назад

Heyy that was a great explanation but can u plz explain the space complexity here..

@CST1992 2 месяца назад

This isn't a Medium problem, but rather an Easy problem, compared to others in the Linked List category I've seen.

@PeachHeartBlog 2 года назад

how does the dummy nodes connect to the head at the first place? Doesn't it something like left.next = head at the beginning? Not totally understand why doing ltail.next = head transfers to left

@codingsavid6509 2 года назад

i got that question too

@nepa8678 Год назад

ltail is reference to dummy

@himanshuchhikara4918 3 года назад

Great explanation , btw nice name neetcode :)

@ahsin.shabbir 2 месяца назад

What if you have to change the original list in-place? This doesnt look like constant space

@vishnugajulapalli5305 3 года назад

Bro, please increase the audio volume while recording, its a bit low. Thanks for the great explanation like always 🙂

@noob-ps2lr Год назад

we are creating only two new node and we are assinging its next to original linked list so space complexity is 0(1)

@abhiarns Год назад

❤

@adityamaskar2147 Год назад

How it is o(1), can anyone tell me?

@ygwg6145 Год назад

Another way: find large elements and move to the end one by one

@gigachad6844 2 года назад

How is this constant space complexity?

@larrasket 2 года назад

In this solution you don't create any new ~ListNode()~ but only the both of ~Left()~ and ~Right()~ nodes, all other linked nodes are already created and initialized from the given list (head).

@jatinpandey6453 5 месяцев назад

@tahichy9169 2 года назад

what is the space complexity here?

@navaneethmkrishnan6374 Год назад

O(1). It might seem like O(n) but we are linking the smaller and larger elements separately only to link them together eventually.

@satyabharadwaj7779 2 года назад

What actually does a ListNode mean by? Is it a linked list or just a node? why is a list being printed when "left.next" is returned in line 22? Can someone explain?

@codingsavid6509 2 года назад

ListNode is a Node only as you can see up there there's a function called ListNode whose attributes are val and next

@satyabharadwaj7779 2 года назад

@@codingsavid6509 can you pls answer the latter part of my comment as well?

@codingsavid6509 2 года назад

@@satyabharadwaj7779 left.next is always the beginning of the list, so you start traversing through it from there in this case, left.next is 1, from there it goes 1 - node - node -node - connects to the beginning of the other then keeps going till the end of the second list

@satyabharadwaj7779 2 года назад

@@codingsavid6509 I get that. But it isn't an iterator by definition, so how would it print a list of items instead of returning a single item is my doubt.

@ultimatecreed5144 Год назад

made it very easy wasted 1 hr on my approach !!!!!

@chaitanyasharma6270 2 года назад

isnt this o of n space

@naive_algorithm 8 месяцев назад

I am using same approach in c++ but it's beating only 6% of solutions😢😢😢

@orellavie6233 2 года назад

Second video where you forgot to init left/right/dummy nodes, they're not pointing to head

@navaneethmkrishnan6374 Год назад

They need not. Only either left or right can point to the head depending on whether it is smaller or larger (or equal to) than x. It is why he uses dummy nodes.