Linkedin Interview Question - Reorder List - Leetcode 143 - Python

0:00 - Read the problem
3:00 - Drawing Explanation
9:23 - Coding Explanation

leetcode 143

#linked #list #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[gackerman]

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.

[amirbayat]

In a real interview, you could say something like:
"I can solve this with O(1) space by finding the middle, reversing the second half, and then merging the two halves. However, I want to note that while this optimizes for space complexity, it creates more complex code with three distinct operations that might be harder to maintain. For a production environment, I might actually prefer the O(n) space solution using an array to store node references, as it's more readable and maintainable, unless memory constraints are a significant concern."
This shows maturity and practical engineering judgment beyond just algorithmic knowledge. Many interviewers actually value this kind of nuanced thinking - it demonstrates that you're considering the broader engineering context, not just solving puzzles.

[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

[aaen]

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

[hwang]

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

[jinny]

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

[mohamadilhamramadhan]

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

[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!

[ranjitprakash]

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

[eddiej]

having the slow and fast starting at different position and set the slow.next to null before rotate it. Is much easier than start them at the same position. Great work

[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

[AdiPrimandaGinting]

In this question alone, I learned three concept: finding the middle point of a singly linkedlist, flipping a linkedlist, and rearranging the linkedlist. These three basics can represent three questions

[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

[shurale]

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?

[elyababakova]

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

[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!

[saralee]

Your channel is soooo helpful. Bless you!

[GoziePO]

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

[tusharsrivastava]

Solved this using stack, much more intuitive.

Store the nodes in a stack.
Connect the start to end and end to start + 1.
Repeat for len / 2 times.

[gsivanithin]

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