[Solution]Problem 75: Reorder List [Meta/Facebook]
LinkedList, Pointer Manipulation, Problem Solving
Hey, it’s your favorite cult leader here 🐱👤
On Thursdays, I will send you a problem + its solution. These solutions will help you reinforce your fundamental concepts, improve your problem-solving, and kill those Leetcode-Style Interviews. 🔥🔥💹💹
To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!
p.s. you can learn more about the paid plan here.
Regarding the poll yesterday,
We have a tie. Currently, it’s a 50/50 between the people who want me to repeat older problems and people who want me to keep those days as free.
If you haven’t already, make sure you go and vote over here. Your vote can be the tiebreaker. Now back to the problem at hand.
This problem can be found as problem 143. Reorder List
Problem
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Constraints:
The number of nodes in the list is in the range
[1, 5 * 104].1 <= Node.val <= 1000
You can test your solution here
Step 1: Simplifying the Problem
As is our wont, we start the hard solution by focusing on a simpler problem first. How can we simplify the problem in a meaningful way, to come up with a better solution later? This is where we refer to a Technique Tuesday written last year, titled The art of making Simplifying Assumptions[Technique Tuesdays]. That has a guide to making the correct simplifying assumptions for product management, software engineering, and Leetcode interviews (amongst others). Specifically, refer to the following passage-
One of the easiest ways to come up with optimal solutions is to sometimes go for the brute force solutions and build up from there. Create the brute force, identify where the solution is inefficient, and fix that specifically. Going straight for the efficient solution is going to require a lot more brain power.
In our case, our computational constraint is pretty clear. IF we could make multiple copies of our list and just copy the right way, then our lives would be much easier. So let’s start exploring that first.
Step 2: Simple Solution
Our simple solution will look something like this-
Traverse the LinkedList and copy it into an array.
Create a new empty LinkedList.
Populate it by alternating between traversing the LL in the normal order and the array in the reverse order.
You stop when your array index crosses the half-way mark.
The more astute amongst you might have noticed one thing. We are traversing the array backward. Why not use a Stack, the traditional Last-In-First-Out data structure? There is a reason I chose arrays. The array indexing makes it easier for us to know when we have crossed the halfway point. Make sure you make this point very clear in your interviews. By doing so you highlight your comfort with DSA, communicate your ability to handle tradeoffs, and handle a question that your interviewer might have preemptively. Talk about a triple whammy 🍔🍔.
This solution will have O(n) time and O(n) space. Not too bad. Can we do better?
Step 3: Improving this
How can we improve our solution? Let’s find the best areas to attack. We know that our solution will most likely be O(n) time complexity since we will have to visit every node. So it makes sense to attack the space complexity and reduce it here.
How can we reduce the space complexity of our solution? One easy way is to replace the benefits that our extra data structures give us and try to replicate them. In our case, the extra data structure gives us two benefits-
The array makes indexing easier, which allows us to find the middle painlessly
The reverse traversal is a blessing. There is no way to do so in a singly linked list.
Let’s attack both of these, one at a time.
Step 4: Replacing our Array
To figure out the middle point of our LinkedList we use a trusty technique in coding, Leetcode, and Computer Science. We rely on two-pointers, one slow and the other fast.
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.nextIf you’re not intimate with this technique, try to convince yourself why this would give you the middle of the LinkedList. This is a great way to understand the technique. Make sure you play around with lots of examples.
Now how can we go through a singly LinkedList in the reversed order?
Look carefully through the solution. I’ve already told you how.
Look through carefully.
Still didn’t get it. Go back and reread what we’ve done so far.
The answer is that.. you can’t. So what can you do (aside from throwing a shoe at me for making you reread the whole post)? Giving up is always an option (in my opinion, a very good one too).
While you can’t go back through a LinkedList, there is one way you can achieve the same result. You can simply reverse the connections. If your LL looks like
A→B, no reason you can’t take a pointer take it to B and then set B.next=A and A.next=null.
How would you accommodate bigger LLs? It’s simpler than you’d think. Try it for yourself, and once you’re done compare it to the code below-
second = slow.next #keep in mind that our slow pointer is at the mid point
prev = slow.next = None
while second:
tmp = second.next
second.next = prev
prev = second
second = tmp Unfortunately, there is no neat and fancy to derive this. This is one of those code segments that you come up with through trial and error. Don’t be afraid to use a little bit of this in your interviews. Speaking from experience, my biggest weakness is that I sometimes get too caught up in trying to come up with a smooth algorithm where some simple trial and error and experimenting on a function iteratively would be better. This mistake has cost me a lot of time and energy in my interviews (and I know other people make this mistake). Fortunately, this is not super hard to come up with after a few trial cases (you’re effectively just swapping nodes).
This snippet will transform your LL-
1->2->3->4->5
Turns into
1->2->3<-4<-5 Fun fact, this is technically a tree (and a graph, if we’re talking mathematically). So what do we do from here? We know that our prev pointer is at the other end of the list (5 in our example). And we still have the head from the original node. So we can simulate the alternating between going in the standard direction and going the reverse way. Now we’re basically done. We just need to put everything together.
Step 5: Putting it all together
Our final solution will look like this-
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
# find middle
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# reverse second half
second = slow.next
prev = slow.next = None
while second:
tmp = second.next
second.next = prev
prev = second
second = tmp
# merge two halfs
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2The merging works in almost the same way as the node-swapping method discussed above.
Time Complexity- O(n)
Space Complexity- O(1)
Loved the post? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.
Stay Woke,
Go kill all,
Devansh <3
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd