Leetcode: Reverse Linked List (Kotlin)

Reverse Linked List is an easy Linked List problem on Leetcode. This is a popular problem asked at Facebook, Amazon, and Microsoft. This problem is also used to solve bigger linked list problems on Leetcode. I will show both an iterative and recursive solution for this problem. Reverse Linked List - LeetCode

Problem Statement

Examples

Constraints

Iterative Solution using a Stack

This was my initial approach to solving this.

Iterate through the linked list and add all nodes to a stack.
Create a dummy node so we can return the head of the list
Iterate through the stack and create a list using each node.
After creating a new list, set the last nodes next to null. The last node was previously the first node, and its next node is still the previous second node. Without doing this, we will have a cycle in the list.
Return the head of the list {% gist https://gist.github.com/cmcoffeedev/50e82f562faa96e6d78b7b14323a5542.js %}

Iterative Solution

After my initial approach, I looked at others’ approaches on youtube, blogs, and the problems discussion tab. The most common solution, which is actually the solution leetcode gives, is to reverse the linked list in place. To understand this better, I used pen and paper to draw out each step. I may redraw my steps to help visualize this.

Create a null previous node to store the reference to this current node before traversing the node again. This will make more sense in the following steps.
We need a current node because the head node is immutable.
While the current node is null, we will traverse through the list
We need to save the next node, because we will replace it in the following steps. It will also be the starting point(current) for each iteration.
Set current’s next node to previous. In the first iteration using the first example listed above, the node with the value 1 will be pointing to null. This is what we want since it will be the last node.
Set the current node as the previous node. Using the first example again, in the second iteration current will be the node with the value 2. We want to set the that node’s next to the node with value one, which will be prev. Drawing out each step helps.
Set the current node to next. As mentioned earlier, this will be the new starting point for each iteration.
After traversing and reversing the list in place, we need to return prev, which is the new head. Prev was previously the last node. {% gist https://gist.github.com/cmcoffeedev/f693e5888bbd2934f3c4fc1dfd1c92d1.js %}

Recursive Solution #1

This is the most popular recursive solution. This is not the first recursive approach I took. It helps to draw the call stack to understand the solution better.

Like the previous in-place iterative solution above, we have a null previous node to start. This will be the head when we are done.
Line 9 is our base case. If the head is null, we will just return the head. This only happens when the head node they give us is null. We also check if the head’s next node is null. This handles the case for when we reach the last node. It will return from the recursive call on line 13.
We need to have a current node since the head variable is immutable.
On line 13, we will set the head to the return value of our recursive call. We pass our current node’s next so that we may continue to traverse the LinkedList.
We will get to line 14 after we reach the end of the list. If we use the first example, the value of the last node is 5. When we return the last node, the current node will be 4. Current nodes next has the value 5. The node with the value of 5 has a next node of null. Instead of pointing to null, we will set the node with the value of 4 to be the next node of the node that has the value of 5. Essentially we are reversing the list two nodes at a time as we are popping up the call stack.
We are also setting the current node's next node to null. The main purpose of this is so the last node’s next value will be null.
Lastly, we return the prev node, which should be the new head.

Again this helps if you draw out each step. {% gist https://gist.github.com/cmcoffeedev/0bfe54d18b8b9938c64051b943fbf2da.js %}

Recursive Solution #2

This was my first recursive attempt. I did this before the above solution. I was going after the common iterative solution but wasn’t sure how I would set the previous one if I set it to null each time in the recursive solution. Therefore, I pass the prev and head each time.

I have previous and current nodes because the head and prev nodes are immutable.
I also save the next node so I may pass it as the new head.
The base case where we check if the current’s next node is null is only used when there is one node in the list. In that case, I will return the current node, which should be the previous and only node.
The second base case is used when there is more than one node in the list. This checks if we are at the last node. If so, we want to set the last node’s next to the current node. We return the next node, which should be the last node.
In our recursive call we use the current node as the prev node and the next node as the new head node, as we traverse down the list. This only happens from the first node to the node right before the last node. {% gist https://gist.github.com/cmcoffeedev/7d0e437a30ac44a1c813351f88a67156.js %}

Runnable solution

{% gist %}