🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

I hate linked list problems. They all reduce to fairly simple ideas made utterly incomprehensible by trying to keep track of sixteen pointers, some significant portion of which are temporary. Just a garbage data structure.

@eliyoung9406

2 ай бұрын

Same

@user-ck6vc4bu4j

8 күн бұрын

Linked List is actually kinda cool

The key to understand this problem is to identify it’s a merging problem, basically the desired sorting can be achieved by splitting the linked list into 2 halves, reverse the second half then merge it in the first half. Wouldn't want to be asked this in an interview tbh :D

@2000daboss

9 ай бұрын

@@tl3231 I don't really understand your question.

@EduarteBDO

8 ай бұрын

I did this question in a complete different way using an array and two pointers. I think my solution was cheating somehow but I don't really know: def reorderList(self, head: Optional[ListNode]) -> None: listStack: list[ListNode] = [] nh = head while nh: listStack.append(nh) nh = nh.next l, r = 0, len(listStack) - 1 while l listStack[l].next = listStack[r] listStack[r].next = listStack[l+1] l += 1 r -= 1 if len(listStack) % 2: listStack[r].next = None else: listStack[r+1].next = None

@coolkaw4497

6 ай бұрын

@@EduarteBDO Wow nice solution!

Linkedlist pointers always make me feel like I'm a dummy. So confusing 😭

@Shubhakar97

Жыл бұрын

I feel you bro 🥲

@mohammedumarfarhan9900

Жыл бұрын

Same here bro. It's been 1 year now howz it going

@DanielRodrigues-bx6lr

Жыл бұрын

Makes you feel like a node yourself huh? . . . . . Joke was that NeetCode likes having dummy nodes in his linkedlist problems dummy = ListNode() Sorry, ik it was a bad joke 😭

@farjanashaik9601

9 ай бұрын

Ya bro 🤦🏻‍♀️

@brij4887

4 ай бұрын

​@@DanielRodrigues-bx6lrCame here to make the same joke but yea, working with linked lists feels like I'm working with assembly

Wow, this one was harder thank it looked. Thanks again for the amazing explanations

This is a great explanation. Linked list questions are generally hard for me to grasp but this vid really explains it so well and straightforward. Thank you so much!

Thanks, man! Top-tier explanation. Your words just went right into my brain. Top quality.

Thanks. I learn something new: break linked list into two parts using two pointers.

Your channel is soooo helpful. Bless you!

Great explanation. Thanks for also mentioning the array approach to solving this problem.

Great solution, however I have a question why didn't you take the general fast and slow ptr algo where in you declare fast and slow both at head? 5:25

Thanks man I asked you yesterday and you got it up today 😍🙌🏼

you made it as simple as possible man, thanks

for merging two lists, can we set first as slow (the first linked list)?

I like this problem. A good one to refresh easy subproblems for linked list. Also, as usual - great explanation!🔥

@priyanshkumariitd

4 ай бұрын

Yeah

Great solution that doesn't take extra memory! Thank you!

You are doing a great job! Keep it up!

Can we do this using recursion ? What would be time complexity of it ?

my first approach was the array based which i know is not inplace, but seeing this approach really feels good especially the fast and the slow pointer one .. great

Thanks! really helpful.. Great videos! One suggestion - Placing/explaining your drawings alongside the code would make it even easier to understand, else its usually pain going back and then again coming back to the code!

conceptually this problem was easy for me. Keeping the pointers straight and where I was at in the lists at each part in the code was the problem for me.

Sometime s and f pointers points to head initially. Sometime they refers to head and head.next. Is there any marker to choose appropriate values to initialise with?

Brilliant solution, thank you!

I used a dictionary to traverse and store the linked list nodes with index location. Then I used left and right pointers to traverse the index and reorderd by pulling the related nodes from the dictionary. It was intuitive to me and one of my first problems I could solve on my own before watching the video

@lakindujay

7 ай бұрын

i tried your method just now, it gave me a different perspective to the problem. thanks!

@Djinn667

7 ай бұрын

how did you do this?

why the initial value of fast is head.next instead of head like the slow pointer? then you don't need to manually adjust slow pointer to slow.next outside of the while loop

Nice explanation! Thanks!

at 12:00 how is second at None when the loop finishes? Is that right?

Initially I used a deque and simply popped from front and back. Of course this has O(n) space complexity, so your solution is better :) Thanks for explaining

@aaqibjavedz2569

11 ай бұрын

I did an array with 2 pointers lol.

@elyababakova2125

11 ай бұрын

good use of deque!

Really good solution, thank you.

slow, fast = head, head also works

Thanks man! Really appreciate that.

If we used recursion, would it still count as extra memory?

thanks for the neet explanation..

heres my slightly different solution class Solution: def reorderList(self, head: Optional[ListNode]) -> None: #find middle slow = head fast = head while fast.next and fast.next.next: fast = fast.next.next slow = slow.next #need node before second half to split list second = slow.next slow.next = None prev = None while second: temp = second.next second.next = prev prev = second second = temp temphead = head while prev: #shorter if odd temp1 = temphead.next temp2 = prev.next temphead.next = prev prev.next = temp1 temphead = temp1 prev = temp2

How did you know that the fast/slow pointer would get you to the center of the list? 5:48 Is this just something you have memorized? Is there some practice I could do to more easily be able to intuit this algorithm?

My idea was to find the midpoint, remove from list and append to a stack, and keep doing this until we're down to the first element of the linked list. Then pop from stack and point cur to the popped node until stack is empty (intuition is that the mid point becomes the last node as we remove an element). It passed 9/12 test causes but timed out unfortunately since it's N^2. stack = [] cur = head while cur.next: fast, slow = head, head slowPrev = head while fast and fast.next: fast = fast.next.next slowPrev = slow slow = slow.next slowPrev.next = slow.next q.append(slow) while stack: node = stack.pop() cur.next = node cur = cur.next cur.next = None

@nihalbhandary162

Жыл бұрын

You could make it O(n) time and O(n) in space. If you just pushed the nodes after midpoint into stack. Then you can pop them back starting from head. (essentially pushing and popping into stack will reverse the later half, and then we just merge them with head to midpoint).

Starting slow and fast both at head works fine as well. No need to `slow, fast = head, head.next` as then you'll need to `second = slow.next` to make up for the lead fast has.

@lemonaut1

Жыл бұрын

bless u i was getting so frustrated trying to understand why he did this

Can you do skyline problem leetcode?

how do you get your leetcode editor in dark mode?

@NeetCode

2 жыл бұрын

Using the top-right settings button, and change theme to Monokai

Test cases don't seem to pass if you try to create a list/array and assign values that way anyway so don't bother with the extra space option.

@kryddan

6 ай бұрын

I used a stack instead, O(N) space of course: def reorder_list(head): stack = [] curr = head while curr: stack.append(curr) curr = curr.next curr = head while True: tmp = curr.next nxt = stack.pop() if curr == nxt or tmp == curr: curr.next = None break curr.next = nxt curr = curr.next curr.next = tmp curr = curr.next

man ur explanation ,great great

i dont know why but it happend to me a couple of times when i struggle with a problem i just open your video and hear hello everyone lets write some more neetcode. the idea of the solution pupup fast :))))

I have doubt here we are using the extra spaces aren't we like left and right linked list

@mohitsinha9090

2 жыл бұрын

No, we aren't using any extra space. If you notice, we aren't duplicating the values. We are just reusing the same memory allocation.

Which platforms do you suggest to draw the explanation???

@adusparx

2 күн бұрын

Excalidraw

i think i am having the hang of it. i mean i understand the question come up with a way to do it, after remembering palindrome problem, clear and concise: # find middle slow, fast = head, head while fast and fast.next: slow, fast = slow.next, fast.next.next # reverse second half(right) pre, cur = None, slow while cur: temp = cur.next cur.next = pre pre = cur cur = temp # reorder list cur = head while cur != pre and pre: temp_l, temp_r = cur.next, pre.next cur.next = pre pre.next = temp_l if pre.next else None cur = temp_l pre = temp_r

if yall don't understand the code at first, try drawing it out. That helped me fully understand it!

very nice problem and decision

Hi , here are two excerpts from two of your solutions for finding the middle element. two different implementations, please can you explain the difference: #1.Reorder linkedList #find middle slow, fast = head, head.next while fast and fast.next slow=slow.next fast = fast.next #2. isPalidrome linkedList #find middle(slow) slow, fast = head, head while fast and fast.next: fast = fast.next.next slow = slow.next

@jamessl1544

2 жыл бұрын

E.g. Linked list head [4,3,2,1]: At the end of #2, slow points to [2,1] At the end of #1, slow points to [3,2,1] This allows him to modify head to be [4,3] by setting slow.next to None. It's just a traversal so modifying slow will modify the original head. In #1 the goal is to get 2 linked lists from splitting the original

@yz-me4tq

2 жыл бұрын

@@jamessl1544 slow,fast=head,head while fast and fast.next: fast=fast.next.next slow=slow.next prev=None while slow: temp=slow.next slow.next=prev prev=slow slow=temp first,second=head,prev while second: temp1,temp2=first.next,second.next first.next=second second.next=temp1 first=temp1 second=temp2 this solution doesnt seem to work. anyone has any idea why?

@jamessl1544

2 жыл бұрын

​@@yz-me4tq # head [4,3,2,1] slow,fast = head,head.next while fast and fast.next: fast = fast.next.next slow = slow.next # head [4,3,2,1] slow [3,2,1] second = slow.next prev = slow.next = None # head [4,3] second [2,1] while second: tmp=second.next second.next=prev prev=second second=tmp # head [4,3] prev [1,2] reversed second first,second=head,prev while second: tmp1,tmp2=first.next,second.next first.next=second second.next=tmp1 first,second=tmp1,tmp2 # head [4,1,3,2]

@kishanbajaj3672

2 жыл бұрын

@Longchi I had the same confusion as you. Keeping both, slow and fast, pointers at the same position in the beginning works for both solutions.

Give yourself a treat by doing it recursive.

Ugh. I understand finding the midpoint and reversing the second half, but merging the two does not make sense to me at all. I dont understand how the pointers are passed around and how it manipulates the head. Ive tried for days just reading through this over and over amd nothing has clicked yet.

I dont understand how input in form of "List" is taken as argument and made it behave like a Linkedlist. I think input list "head" needs to be converted first to Linkdlist first and then taken as argument. Can someone help me explain how thing work ?

@EverydayAwes0me

Жыл бұрын

I see your confusion as the input examples may suggest that a Python list of those numbers is being passed to the function. This list is not what is really passed into the function, it simply a visualization of the values in the linked list. Head is really the first node in the linked list.

hi man i want to learn basics of linklist in python from where i can learn that?

@alexandreyano7809

2 жыл бұрын

You can start from here: kzread.info/dash/bejne/eIen1MuQgZPXiag.html

@Billy69271

2 жыл бұрын

@@alexandreyano7809 thanks for the link!

Where are subtitles?

Not sure if anyone else also created a generic reverse list helper, included mid in the second half and got infinite loops. My understanding is that if we do so, there is no way of removing the connection between the first half and the reversed second half(without adding another iteration)

@Shiro-vh5oh

Жыл бұрын

a generic reverse list helper could work, just need to say 'while second.next' instead of 'while second'

I need to get my hand running on these fast slow pointer questions. Can someone suggest me some similar fast slow pointer questions?

@abdou-3h

2 жыл бұрын

Find the middle of a linked list Linked List Cycle

I hate linked list problems

I came up with a solution that ran in quadratic time pretty quickly but it didn't get accepted on leetcode and that's why I had to watch this video

Tha was tricky. it seemed like an easy problem but god was i wrong!

class Node: def __init__(self, data): self.data = data self.next = None def reverse(head): curr=head prev=None while curr is not None: temp=curr.next curr.next=prev prev=curr curr=temp return prev def rearrangeList(head): temp=head while temp: temp.next=reverse(temp.next) temp=temp.next return head

Could someone explain why we don’t have to actually return anything? Why is setting first=head sufficient?

@countdooku681

2 жыл бұрын

Because we never modify the first one node actually, so there's always persist a link to this node in the outer world of our function.

@ashs3979

2 жыл бұрын

@@countdooku681 Thank you 🙏

@Music-tp8gg

2 жыл бұрын

Because the return type is void.

@abhicasm9237

2 жыл бұрын

Because objects are referenced types. So any change to them will be reflected to the same memory. So you don't need to return them

How it can be so magic and so simple at same time?

Can someone explain why slow.next =None?

@saptarshidas488

2 жыл бұрын

the last node of first part of the linked list becomes the last node of the reordered list, so next variable of that node (whose reference is stored in the slow pointer) is initially set to None

Can someone explain why fast starts from head.next, not head?

@SauerChef

2 жыл бұрын

I think either way works, but syntax is a little different. If you use fast=head, you won't need to set "second = slow.next", instead second will just be slow. You can draw it out and it will be more clear! (Anyone please correct me if I'm wrong)

@countdooku681

2 жыл бұрын

You can easily start with head. You just need to modify your while loop so it runs while your fast.next && fast.next.next are true.

@orangethemeow

2 жыл бұрын

Only changing the initial condition fast = head without changing anything else also works. I'm also confused here

@mkum2141

Жыл бұрын

@@orangethemeow this is also confusing me, did you figure out why?

@dumbfailurekms

Жыл бұрын

@@mkum2141 Hey I figured this out if anyone in this thread still cares 5 months later. I assume by now you all have figured it out too though. ;p

Pretty cool problem

I dont know why but i found linked lists problems much harder than trees problems, despite trees are some sort of evolution of linked lists

This messed with my head

understood

Why do we need line 14 + 15? (second = slow.next) and (slow.next = None)? Is it because we have to return in place, so the original list can't be altered?

@The6thProgrammer

10 ай бұрын

The original list is being altered (the nodes themselves are being changed to point to different nodes). By setting second = slow.next we are storing the head of the second list. Once we have stored the head of the second list safely, we are setting slow.next = None since slow is the last node in our first list, it should be pointing to None. So for a list such as 1 -> 2 -> 3 -> 4 -> 5 -> nullptr, the new result after these 2 operations is 1 -> 2 -> 3 -> nullptr for the first list and 4 -> 5 -> nullptr for the second.

@user-kf5uz6rw4w

4 ай бұрын

@@The6thProgrammer so basically slow pointer modifies the head list. But why does the fast pointer not modify the head list?

NeetCode, could you experiment with having your drawing solution in sync while coding. Assimilation would be faster and we will know why you applied a certain logic

@GoziePO

9 ай бұрын

I just tried drawing for myself while he was coding and it helped alot in understandingthe logic

best ever

@AnnieBox

3 жыл бұрын

Yea, absolutely BEST ever!!! 👍

leetcode problems are killing me

I did this question in a complete different way using an array and two pointers. I think my solution was cheating somehow but I don't really know: def reorderList(self, head: Optional[ListNode]) -> None: listStack: list[ListNode] = [] nh = head while nh: listStack.append(nh) nh = nh.next l, r = 0, len(listStack) - 1 while l listStack[l].next = listStack[r] listStack[r].next = listStack[l+1] l += 1 r -= 1 if len(listStack) % 2: listStack[r].next = None else: listStack[r+1].next = None

crazy

he sounded so different back then

@eliyoung9406

2 ай бұрын

not really lol

void reorderList(ListNode * head) { vector v; ListNode * temp=head; while(temp!=NULL) { v.push_back(temp->val); temp=temp->next; } ListNode * tail=head; int start=1 , last=v.size()-1; while(startnext=newnode1; tail=newnode1; tail->next=newnode; tail=newnode; start++; last--; } if(v.size()%2==0){ ListNode * newnode1=new ListNode(v[last]); tail->next=newnode1; tail=newnode1;} tail->next=NULL; } T.C=O(n) S.C=O(n)//this is not the optimized answer this was the first answer discussed in the video

my first attempt for this problem was a rather bruteforce lol repeat following until head.next.next is not None: head -> (reverse the rest of list) so if we have 1-2-3-4-5 1 -> (5-4-3-2) 1 -> 5 -> (2-3-4) 1 -> 5 -> 2 -> (4-3) 1 -> 5 -> 2 -> 3 -> (4) but this was too slow :(

Another simple way to solve this with using extra space is create the array, then just alternate pop() and poll() to assemble the linked list.

esto ya no funciona :(

@luiggymacias5735

4 ай бұрын

como?

@wotizit

4 ай бұрын

estas

lmao, guess what, I solved this problem and it turned out to be LeetCode daily.... What's the chance of that happening?

Am I the only one that lowkey likes LinkedList problems. Definitely prefer them to Trees

intelligent

I solved it storing only half of the nodes def reorderList(self, head: Optional[ListNode]) -> None: list_len = 0 node = head while node is not None: list_len += 1 node = node.next half: list[ListNode] = [] i = 1 j = list_len//2 - 1 node = head while node is not None: node_next = node.next if i

If it helps you to better visualize this problem, instead of fast and slow pointer you can just count all the elements first, than iterate until the size/2 or size/2+1 th element (depends if the size is even or odd).

wamtde

Absolute madness. I can't grasp anything. Linked lists are delusional

hiohlihlhilhilhilhlihilhilhilhlihlihlihilhlisexz

Companies should no longer hire based on this stupid crap that Copilot can easily do.

While most of your videos are usually top notch, I am disappointed in this video. You do not do this algorithm justice by explaining it properly. Your lazily attempt at explaining the algorithm just gets overshadowed because “now here’s the code surely you all can understand it”. We can’t. An animation of the algorithm would’ve been helpful, instead your 5-year-old drawings were presented and we are expected to understand what’s going on.

@dumbfailurekms

Жыл бұрын

mad cus bad

@buttofthejoke

6 ай бұрын

Oh my goodness. I guess you should be disappointed at yourself. To understand this problem, you simply need to know 1. traversing a linked list 2. Using slow and fast pointers to reach the midpoint of a LL 3. Reversing a LL All these are easy level questions that have already been discussed in this channel. You can't expect someone to explain all basic concepts in each and every problem. And you're expressing your disappointment as if YOU are owed a detailed explanation

@dumdum407

3 ай бұрын

skill issue