Ace Your Coding Interview- Blind 75 Solved and Explained — Part 4 Linked List

13 min readJun 19, 2022

This week we are going to be focusing on the data structure of a linked list. Before looking at these questions work I highly recommend understanding how linked lists themselves function. By understanding how progress in a linked list we can understand what are the best approaches to solve questions. All the questions below deal with a singly linked list so we only need to worry about the next pointer.

As always the link to the Blind 75 is below:

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

www.teamblind.com

Question 1 — Reverse Linked List

Reverse Linked List - LeetCode

leetcode.com

Our first question is another famous interview question that is very simple but often overlooked. For this question we have to reverse the linked list we are given and return the head of the new linked list. Hopefully having understood the general structure of a linked list, in a singly linked list we can only move forward. This complicates things a little. How can we only move forward and reverse a list?

Our Approach:

We need to declare two nodes, these nodes will help point to our current and previous node in our linked list. As we are declaring these nodes we need to set our current node to the head of the linked list as it is the first element. Since we don’t have previous elements we can set that to be null.
We need to loop through our list till we reach the end of it. Well, how do we know we have reached the end? Pretty simple actually, if our current element gets pushed forward and no longer points to any data–meaning points to null–this means we have reached the end of our list.
Next, we need to develop our inner loop. First, we need to determine what our next element is. This way at any given point we will have access to our previous, current, and next element. Now next step, how do we do the inverting itself.
A little visualization helps here. Imagine
Head (1) → 2 → 3 → 4 → null
We want to make the list look like the following:
Head(4) → 3 → 2 → 1 → null
Which is the same as
null ← 1 ← 2 ← 3 ← Head(4)
Do you see how the first diagram is similar to the last one only the arrows are flipped? Perhaps we can solve this problem by just flipping our arrows? So we are going to take our current element and point it to our previous element.
Now our list looks like this: Head (1) ← 2 → 3 → 4 → null.
We flipped our pointer, now we need to update our previous and current nodes so we can repeat this process. To do this, we set our previous node to the current node and set our current node to the next node. By the end of this operation, both the previous and current nodes got pushed forward by one element.
Finally, at the end of this operation, we need to return an element. We don’t want to return our current element as that would be null; instead previous element is pointing to the last element we had dealt with which is now the new head of our linked list.

Question 2 — Linked List Cycles

Linked List Cycle - LeetCode

leetcode.com

For this question, we are going to determine if a list is cyclical. What does this mean? Imagine this as the last node of the list pointing to the first node. This way there is no null in the list and it is cyclical. This type of question also introduces us to the concept of fast and slow nodes, a concept that is often used in more complex linked list problems.

Our Approach

We are going to need 3 nodes: slow, fast, and head. These nodes are going to serve us as pointers as we loop through our linked list.
We need to iterate our list to see if our list is cyclical. But what kind of conditional statement do we require for our iteration? As you remember from us discussing the question from our approach we can’t have a null in a cyclical list. Therefore, as we loop we can check if our fast pointer itself (a.k.a our leading pointer), or the next pointer is null. If it is null that means there is a break in our list meaning it's not cyclical.
Now for the concept of fast and slow pointers. We are going to have a slow node that moves forward by one node and a fast node that moves forward by two nodes at a time. Now you may ask why we do this. This is much easier to explain using a simple analogy. Imagine a track and two athletes. Considering we have a regular track that goes around in circles. If our fast athlete runs twice as fast as our slower athlete, the fast athlete will eventually lap the slower athlete. This is the same principle we are going to use. We are sending a node twice as fast and checking to see if it catches up to our slower node.
With that being said we are going to check if the slower node and the faster node meet at any point. If they do this means we found a cyclical list. Thus, we return true.

Question 3 — Merge Sorted Linked List

Merge Two Sorted Lists - LeetCode

leetcode.com

For this question, we are going to get two sorted lists and combine them into one sorted list. If you have ever combined two sorted arrays to create one sorted array it uses similar principles. We are going to work our way through the two arrays selecting what should be inserted into our merged array and being returned.

Our Approach:

We are going to need to create a new list to return once we have accomplished all our operations. To do this we are going to declare a new list with just a simple 0 node and then assign a pointer p to look directly to the new list.
Like all the previous questions, as we are working with a linked list we need to use a method of iteration. For we are going to iterate until both of our lists being merged is empty. To check for this we are just going to check if both list one and list two are null.
After checking we pass the conditional statement of our iteration, we need to evaluate to see which node we are going to add to our merged list. This is quite straight forward we need to determine if the value of the head of list one or list two is bigger. We make a small statement to see if list one value is greater than list two value. If list one is found to be greater, we set the next pointer of our return list to list two. Then we need to push the head of list two forward one since we added the current head element into our merged element.
If list two is found to be greater we do the opposite of before. Set the next element of our merged list to the head of list one, and push the head of list one forward by one element.
After we complete adding a node to our merged linked list we need to push our current pointer forward by one element. This will set our pointer to be empty and enable us to add the next element to our merged list.
What happens once our iteration is over? If our iteration is over that means one of 3 things occurred: list one is empty, list two is empty, or both lists are empty. So we need to check which lists are empty. If list one is empty, add all the remainders of list two; if list two is empty add all the remainders of list one.
Finally, we need to return our new merged list. Since we needed to create a dummy node of 0 to initiate our list we can get rid of that node by pushing the head of our merged list forward by one element. Then we can just return our merged list.

Question 4 — Merge K Sorted Lists

Merge k Sorted Lists - LeetCode

leetcode.com

In the previous question, we combined two ordered lists into one merged list. Now we need to merge an unknown amount of ordered lists into a merged list. To come up with the most straightforward solution in my opinion we are going to utilize some simple lambda operations and a priority queue. The trick to working out this question is always being able to pull out the smallest number from a possible set of selections

Our Approach:

First, we need to check if we can proceed with this method, so we check the edge case where we have 0 lists. If we have no lists we can just return null for our result.
Next, we are going to create a priority queue that is going to work as a minimum heap. Every time we poll this priority queue we should receive the smallest element available.
We need to populate our priority queue to poll from it. To do this, we are going to iterate through all available lists in our lists array and individually add their elements into the priority queue.
So for each linked list within the lists array, we are going to offer the current node to the heap and iterate one node forward and keep doing this operation until we reach the end of the current list.
Next, we have to create the list itself that is going to be returned. This can be done like before where we declare a dummy node and have the head pointing to the dummy node.
After we have declared our list, it’s time to populate it utilizing our priority queue. Like any other queue/stack we are going to iterate through our queue until it's empty.
In each iteration we are going to poll the priority queue giving us the smallest possible element, we are going to place this element into our return list by pointing our head’s next pointer to the polled element. We also have to set the head one node forward so we can add elements for our next iteration.
Finally, we are going to return our original list by just returning the next pointer in the dummyNext list.

Question 5 — Remove nth from the End

Remove Nth Node From End of List - LeetCode

leetcode.com

This is another question that looks at our understanding of multiple pointers. When we combine a few points in our knowledge the question almost solves itself. What points of knowledge are we combining you ask? We know a singly liked list ends in a null. We know we can send pointers ahead of others by as much as we would like.

Our Approach:

To attempt these questions, we need to create a few variables that are going to help us track where we are on the list. So we need to keep a dummy node to point to the head of our list. On top of this we need a first and a second node; imagine these almost like fast and slow nodes. Both of these pointers point to the dummy itself.
This question requires two types of iterations, In the first iteration, we are going to send our first pointer down n elements. This can be done with a simple for loop and with every iteration in the for loop we just push the first node down one by one. By iterating n times we have pushed our first pointer n forward. The reason we do this is now we have created n spaces between the first and second elements.
Now for our second iteration, since we have a space of n between the first and second element we put ourselves in the perfect spot. If we push both these elements forward with the same amount of iterations by the time the first element reaches the end the second element will be n elements away from the end. Subsequently, we can create a while loop with the conditional statement of the first doesn’t equal null. First being null just indicates to us that we reached the end of our list. So until our leading element reaches the end of the list we are just going to push both our leading and trailing element down an equal amount.
Now that we have set our element n away from the end we can solve the question by deleting the nth element from the end. This is a simple pointer maneuver, if we set the next pointer of our trailer element to point down two next elements it will ignore the element in the middle. Thus, having deleted the element in the middle as no element is pointing at it. Java garbage collector will take care of it.
Finally, return your dummy.next which has been pointing to your original list since the start.

Question 6 — Reorder List

Reorder List - LeetCode

leetcode.com

The biggest issue with this question is understanding what is being asked. Even though it's straightforward when being shown in the question section wrapping your head around exactly what's being asked takes a second.

Our Approach:

Like always check for our edge case of nothing existing. For this question, we also need to check if we only have one element. The reason being one element cannot be rearranged.
Three clear distinct steps are needed for us to solve this question. First, we need to find the middle of our list. This can be done by using a leading and trailing pointer once again. We can send our leading pointer down the linked list with twice the speed as the trailing pointer. So by the time the leading pointer has made it to the end of the list the trailing pointer is only halfway. Thus, the trailing pointer is the halfway point. I am not going to go into the depth of setting up the iteration function it was previously discussed in the cyclical question.
Next, we need to reverse the half after the middle point. Lucky for us, I remember us reversing a list earlier in the article. With a similar approach, as the first question, we are going to reverse the second half of our list. Like before the process for that can be found further up in the article as explaining it again would be repetitive. We should also break the link between the first and the second half of the list to have different lists that we can merge.
When these are done we can get to the part that truly differentiates this question — the reordering. How do we get from where we are at to the solution. So it's going to take a second to wrap your head around it. Right now we have two pointers one pointing to the beginning of our list and one pointing to the beginning to the second half of the list. Now we are going to start our iteration; we are going to check when either our first half or second half of the list reaches its end.
Essentially what we want to try and do is to have the item from our first half point to the corresponding element in the second half.
For example, 1 → 2 → 3 and 6 → 5 → 4 Notice how there is no link between the two lists as it was broken in the previous step. We are going to store two pointers so we can reference them after finishing our swap. In this instance we are going to store the elements our heads need to point to — let’s call this tmp1 and tmp2.
We are going to start our list arrangement by accessing the head of the reversed list and pointing to what the original head is pointing towards. So in our example above, 6 now points to 2.
Now we need to update our original head to point to what was the beginning of the reversed list. So now 1 point to 6, and our lists look like this: 1 → 6 → 2 → 3 and 5→ 4. See how the first list looks more list the one we need.
Remember how we cached the elements that we would need in the future, referring back to these elements we can move our pointers forward in our list. So now we have a pointer pointing at 2 (the second item on the original list) and 5 (the second item on the reversed list.) We can use this again to iterate one more time through the list.
Once the iteration ends we have a rearranged list.