LESSON 277 OF 348 · LINKED LISTS

Reverse Linked List in Kotlin: O(n) Time, O(1) Space

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example:

Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

Hints:

This problem is avery similar to "Reverse String" problem, so it's natural to think of adapting that solution for Linked Lists. Unfortunately, traversing with two pointers doesn't work here because the right pointer should move to the left, and we cannot do that in a Linked List. The trick is actually in modifying the links of our Linked List to obtain its reversed version. How should we modify them?

We just have to reverse each link in the list. For example: 1 -> 2 -> 3 -> 4 should become 1 <- 2 <- 3 <- 4. And the head of the reversed list is the tail of the original one. How can we reverse these links?

One idea is to traverse the list from left to right using a variable node and convert each link node -> node.next to node.next -> node:

node = head
while node:
  nextNode = node.next
  nextNode.next = node
  node = nextNode

But there is a problem with this algorithm. Can you find out what that is? Take some small example and run it by hand.

The problem is that the moment we reverse a link, we lose access to the next nodes. For example, if the list is 1 -> 2 -> 3. When node is 1, we reverse the link and the list becomes 1 <- 2 3. We lost the link between 2 and 3. And so at the next step node becomes 2 but node.next is 1 instead of 3. The solution is still good, but we need to implement it in such a way that this problem is fixed.

We should traverse the linked list, while using two pointers:

prev - the previous node
node - the current node

We will start with the first two nodes in the list: prev = head and node = head.next Then, for as long as node != NULL, we will reverse the link prev -> node and update the two variables such that they point to the next two nodes. Can you figure out how to code this? Take the example above and figure out how you should update the pointers after each link reversal.

prev = head
node = head.next
while node:
  	nextNode = node.next
	node.next = prev
	prev = node
	node = nextNode

STEP 1 OF 9

Guided

Ctrl + Enter to check

Reverse Linked List in Kotlin, explained

Problem overview

The function reverse receives the head of a singly linked list as a ListNode? and returns the head of the reversed list. For the list [1, 2, 3, 4, 5] the result is [5, 4, 3, 2, 1]. The statement asks for O(n) time and O(1) extra space, so the function must not copy the values into another structure. It has to rewire the existing nodes.

Approach: flip every link, but save the next node first

With two pointers you can reverse an array by swapping from both ends, but that needs a right pointer that moves left, and a singly linked list only has links that go forward. The idea here is different: reverse each link. Where node 1 points to node 2, make node 2 point to node 1. The old tail then becomes the head.

The naive version walks the list and sets node.next.next = node. It fails because the first rewrite destroys the way forward: once node 2 points back at node 1, nothing leads from node 2 to node 3. The fix is to remember where you are going before you change anything.

The algorithm uses three references:

prev, the node before the current one, which becomes the new next of the current node;
node, the node whose link is being flipped;
nextNode, the node after node, saved before the flip.

Here is the run on 1 -> 2 -> 3. At the start, prev is node 1, node is node 2, and node 1's link has been cut. In the first pass, nextNode is node 3, node 2 now points to node 1, then prev becomes node 2 and node becomes node 3. In the second pass, nextNode is null, node 3 points to node 2, prev becomes node 3 and node becomes null. The loop stops, and prev is the head of 3 -> 2 -> 1.

Step by step

Declare prev as a var set to head. It follows the current node and starts on the first node.
Declare node as a var set to head!!.next, the second node. The first node is handled before the loop. The !! asserts that head, whose type is ListNode?, is not null; the lesson never passes an empty list.
Cut the first node's link with head.next = null. This node ends up as the last node of the reversed list. If it kept pointing at the second node, the result would end in a cycle. No !! is needed here, because after the one on the previous line Kotlin knows head is not null.
Loop while node != null. Inside the loop, Kotlin treats node as a non-null ListNode.
Save the rest of the list in nextNode, a val, set to node.next. Without this, rewriting node.next would lose every node after node.
Flip the link: set node.next to prev.
Advance prev: set it to node. This must come before moving node, or the current node would be lost.
Advance node: set it to the saved nextNode.
Return prev. When the loop ends, node is null and prev holds the last node processed, the new head.

The solution in Kotlin

class Solution {
    fun reverse(head: ListNode?): ListNode? {
        var prev = head
        var node = head!!.next
        head.next = null
        while (node != null) {
            val nextNode = node.next
            node.next = prev
            prev = node
            node = nextNode
        }
        return prev
    }
}

The Kotlin details worth a closer look:

Nullable types. A parameter of type ListNode? may be null, and Kotlin refuses to read head.next until it knows otherwise. head!! is that promise; it throws a NullPointerException at run time if the promise is false.
Smart casts. After head!!, the compiler remembers that head is not null, because it is a function parameter and cannot be reassigned. In the loop, the test node != null does the same for the local variable node. A property such as node.next is mutable, so the compiler does not smart-cast it; only local variables and parameters get that treatment.
Inferred types. var prev = head has type ListNode?, so it accepts both nodes and null. var node = head!!.next is also ListNode?, because next is nullable.
The list is changed in place. The nodes are objects, and the function rewrites their links. After the call, the original head variable still refers to the first node, which is now the last: its next is null.

Complexity

Time: O(n). The loop runs once per node after the first, and each pass does a constant amount of work.

Space: O(1). Only the references prev, node and nextNode are created, no matter how long the list is. A recursive solution would use O(n) stack instead.

Edge cases and common mistakes

A single node. The list [7] gives node = null straight away, the loop is skipped, and prev, the same node, is returned.
Two nodes. [1, 2] becomes [2, 1] after one pass of the loop.
An empty list. The reference solution calls head!!, so a null head throws a NullPointerException. The lesson's lists are never empty. To support an empty list, start with var prev: ListNode? = null and var node = head and drop the special handling of the first node.
Forgetting head.next = null. The old first node would still point at the second node, and the reversed list would end in a cycle between those two nodes.
Not saving nextNode. Flipping the link first loses the rest of the list.
Updating in the wrong order. If node moves before prev does, prev never catches up with the node just processed.
Returning head. The old head is now the tail. Return prev.

Testing

[1, 2, 3, 4, 5] gives [5, 4, 3, 2, 1].
[1, 2] gives [2, 1].
[7] gives [7].

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free