Linkedin Interview Question - Reorder List - Leetcode 143 - Python

[@NeetCode]

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

[@gackerman99]

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]

Same

[@Hrishikesh-p5n]

Linked List is actually kinda cool

[@pun1sher98]

Although I understand your frustration, LLs are used as a primary data structure in most of the embedded systems. So its good to have knowledge of this!

[@souljarohill8795]

felt

[@Hoppitot]

just put the nodes into a vector and be done with it lmao

[@m_elhosseiny]

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]

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

[@EduarteBDO]

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 < r: 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]

@@EduarteBDO Wow nice solution!

[@luizferreira3986]

@@EduarteBDO I think thats because you transformer a linked list problem into a list problem

[@raghavdewangan6585]

@@luizferreira3986 yeah the space complexity suffers, but still a good solution. always good to have new ways to do things, even if its not the most efficient, opens up your way of thinking.

[@jinny5025]

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]

Ya bro 🤦🏻‍♀️

[@brij4887]

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

[@aaen9417]

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

[@hwang1607]

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

[@AndrewCJXing]

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!

[@mohamadilhamramadhan6354]

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

[@Deescacha]

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]

I did an array with 2 pointers lol.

[@elyababakova2125]

good use of deque!

[@ranjitprakash1986]

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]

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

[@Djinn667]

how did you do this?

[@dang5571]

nice, i also thought this problem reminded me of a two pointer problem so im glad im not the only one

[@saliherenyuzbasoglu5819]

what is the point of linked list if you are going to use another data structure with size n

[@tonyiommisg]

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.

[@kaushal__]

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!

[@gsivanithin]

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

[@aynuayex]

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

[@saralee548]

Your channel is soooo helpful. Bless you!

[@Xeoncross]

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

[@elyababakova2125]

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

[@priyanshkumar17]

Yeah

[@GoziePO]

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

[@pravatbiswas]

slow, fast = head, head also works

[@adityabhattad4614]

Recursive solution is easier class Solution: def reorderList(self, head: Optional[ListNode]) -> None: temp,temp1 = head,head while temp and temp.next: temp1 = temp temp = temp.next if head==temp or head.next==temp: return temp.next = head.next head.next = temp temp1.next = None self.reorderList(temp.next)

[@YouProductions1000]

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

[@omaryasin9330]

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

[@souljarohill8795]

its an easy data structure but the way this problem has you solve it makes it complex. so many different pointers

[@myosubug]

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

[@shurale85]

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?

[@vwgli1998]

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

[@arijkhan9173]

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

[@TenzDelek]

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

[@aadityasurana6396]

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

[@maamounhajnajeeb209]

you made it as simple as possible man, thanks

[@quranic.verses1]

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

[@adusparx]

Excalidraw

[@quirkyquester]

for those who are wondering why we starts the code with head, head.next, cos we need to get to end of the first half, point it to none, we also need access to second half, so this way it make things easier for us.

[@rahulsbhatt]

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

[@moonlight-td8ed]

thats how they generally work.. dont they?

[@rahulsbhatt]

@@moonlight-td8ed yeah, I don't know what I was thinking....

[@Hytpu9]

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

[@RandomShowerThoughts]

hm, I think using a stack here makes the most sense imo. That way we have an easier way of tracking what we visited, though you need to create a wrapper. ``` type element struct { idx int node *ListNode } func reorderList(head *ListNode) { mid := findMiddle(head) midHead := reverseLinkedList(mid) l := head r := midHead for l.Next != nil && r.Next != nil { lTmp := l.Next rTmp := r.Next l.Next = r r.Next = lTmp l = lTmp r = rTmp } } func reverseLinkedList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } h := reverseLinkedList(head.Next) head.Next.Next = head head.Next = nil return h } func findMiddle(head *ListNode) *ListNode { slow := head fast := head for { if fast == nil || fast.Next == nil { return slow } fast = fast.Next.Next slow = slow.Next } } ```

[@longchikanouo4905]

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]

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]

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

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

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

[@quirkyquester]

the best solution online, leetcode solution doesn't explain well about how it avoids the infinite linkedlist, it just gives a magic code.

[@sucraloss]

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]

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

[@charleszhao3464]

I hate linked list problems

[@bar.binyamin]

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

[@ishtiaquehussain]

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

[@MerrowGula]

Give yourself a treat by doing it recursive.

[@johndanek3130]

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.

[@jkk23-g7c]

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

[@jerremy7]

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?

[@RuslanZinovyev]

Actually it's well-known algorithm, you should know this if you wanna solve LL problems. The good news is it's pretty straightforward.

[@RandomShowerThoughts]

this man is truly the

[@smtp_yurzx]

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]

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

[@siddhantsehgal9900]

You are doing a great job! Keep it up!

[@unknownboy8174]

Thanks alot bro for all your efforts

[@EduarteBDO]

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

[@jritzeku]

Kind of confused...what is ultimately being returned if we dont have to do it ourself? If you return 'first' it now points to null. To make it explicit, i used the dummy node instead and returned it. dummy = head //find middle, //reverse //merge return dummy

[@adityachache]

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

[@brucetsai5896]

Really good solution, thank you.

[@2000daboss]

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

[@MohamedAdel0312]

Brilliant solution, thank you!

[@alexdatcode674]

how do you get your leetcode editor in dark mode?

[@NeetCode]

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

[@digestable_bits]

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'

[@ShaneKluskowski716]

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.

[@nehaa3778]

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

[@ritikgupta1133]

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

[@НикитаБуров-ъ6р]

very nice problem and decision

[@QVL75]

Nice explanation! Thanks!

[@student_03]

that was amazing thank you

[@pariminaresh2862]

thanks for the neet explanation..

[@algorithmo134]

Can you do skyline problem leetcode?

[@meherhasanth3450]

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

[@hemesh5663]

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

[@mohitsinha9090]

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.

[@Music-tp8gg]

Thanks man! Really appreciate that.

[@katielee3620]

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

[@kewtomrao]

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

[@nagasivakrishna5660]

man ur explanation ,great great

[@neha_tatpuje]

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.

[@Ruslanpv6bs]

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

[@moeheinaung235]

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

[@h3ckphy246]

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

[@s8x.]

leetcode problems are killing me

[@AndreiSokolov-k7j]

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

[@devmahad]

thanks :)

[@minyoungan9515]

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

[@SauerChef]

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]

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]

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

[@scurgames]

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]

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.

[@shaharrefaelshoshany9442]

best ever

[@AnnieBox]

Yea, absolutely BEST ever!!! 👍

[@spector7588]

Where are subtitles?

[@abhicasm9237]

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]

Find the middle of a linked list Linked List Cycle

[@MIDNightPT4]

Pretty cool problem

[@itzvivi4256]

Can someone explain why slow.next =None?

[@saptarshidas488]

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

[@illu1na]

why is first fast not head or head.next.next?

[@indhumathi5846]

understood

[@user-nq7nt1rq9b]

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

[@alexandreyano7809]

You can start from here: kzbin.info/www/bejne/fITWo5yNhpWkj6c

[@Billy69271]

@@alexandreyano7809 thanks for the link!

[@ashs3979]

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

[@countdooku681]

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]

@@countdooku681 Thank you 🙏

[@Music-tp8gg]

Because the return type is void.

[@abhicasm9237]

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

[@pastori2672]

he sounded so different back then

[@eliyoung9406]

not really lol

[@mojojojo1211]

This messed with my head

[@piglovesasy]

intelligent

[@John-g8d]

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

[@tsunningwah3471]

crazy

[@anabelberumen]

esto ya no funciona :(

[@luiggymacias5735]

como?

[@wotizit]

estas

[@torvic99]

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

[@tsunningwah3471]

wamtde

[@Josh-tu9ji]

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]

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]

skill issue

[@tsunningwah3471]

hiohlihlhilhilhilhlihilhilhilhlihlihlihilhlisexz

[@ericsodt]

This explanation makes zero sense.