Start learning free

LESSON 301 OF 414 · LINKED LISTS

Reverse Linked List in Scala: O(n) Time and O(1) Space

Practice O(n) Read the full explanation

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 very 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. In plain steps: start with node at the head; while node is not null, set nextNode to the node after node, make that next node point back at node, then move node forward to 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 is the head and node is the node after the head. Then, for as long as node is not 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.

Start with prev at the head and node at the node after it. While node is not null:
  • save the node after node in nextNode;
  • make node point back at prev;
  • move prev to node;
  • move node to nextNode.
Don't forget to cut the old head's link to the second node, so the reversed list ends there, and return the new head.

STEP 1 OF 9
    Ctrl + Enter to check

    SCALA · LINKED LISTS

    Reverse Linked List in Scala, explained

    Problem overview

    The method reverse receives the head of a singly linked list 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 method can't copy the values into a second structure. It has to change the links of the existing nodes.

    Approach: flip each link, but save the rest first

    Reversing the list means making every node point to the node that used to be before it. The old head becomes the last node, and the old last node becomes the new head.

    The first idea is to walk the list and, for each node, rewrite node.next so it points backwards. That has a trap. The moment node.next is overwritten, the reference to the following node is gone, and the rest of the list can no longer be reached. On the list 1 -> 2 -> 3, flipping the link of node 1 gives 1 <- 2 and leaves node 3 unreachable from the loop.

    The fix is to remember the next node before changing anything, and to carry the node behind the current one so the flipped link has somewhere to point. The loop therefore uses three references:

    • prev, the node behind the current one (the part of the list already reversed ends here);
    • node, the node whose link is being flipped;
    • nextNode, a saved copy of the node ahead.

    Each iteration flips one link and moves all of the references one step forward. Every node is visited once and no new nodes are made, which gives O(n) time and O(1) space.

    On 1 -> 2 -> 3, start with prev = 1 and node = 2, and cut the old head so it ends the list: 1 -> null. Iteration one saves node 3, points 2 back at 1, then moves: prev = 2, node = 3. Now the reversed part is 2 -> 1. Iteration two saves null, points 3 at 2, then prev = 3 and node = null. The loop ends, and prev holds 3 -> 2 -> 1.

    Step by step

    1. Declare prev with var and initialize it with head. It is the node before the current one.
    2. Declare node with var and start it at the second node, head.next. The head itself is handled in the next step.
    3. Cut the head's link: head.next = null. The head becomes the tail of the reversed list. If it kept pointing at the second node, the reversed list would end in a cycle.
    4. Loop while node != null.
    5. Save the rest in nextNode, declared with val because it is never reassigned. Without it, writing to node.next would lose every node after node.
    6. Flip the link: set node.next to prev.
    7. Advance prev: the current node becomes the previous one.
    8. Advance node: set it to the saved nextNode. Update prev first, then node; the reverse order would lose the current node.
    9. Return prev. When the loop ends, node is null and prev is the last node that was processed, which is the head of the reversed list.

    The solution in Scala

    class Solution {
    def 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
        }
        prev
    }
}

    The Scala details worth a closer look:

    • var versus val. prev and node change on every iteration, so they are var. nextNode is created fresh in each iteration and never reassigned, so it is a val. The type of each is inferred as ListNode.
    • Mutable fields. node.next = prev only compiles because next is declared as a var field of ListNode. The method modifies the caller's nodes, so the original list is destroyed. After reversing 1 -> 2 -> 3, the old head (the node 1) is the last node, and following next from it gives null.
    • The last expression is the result. The method ends with prev, and Scala returns it without a return keyword.
    • null checks. node != null compares references, and != in Scala also works on null without throwing.

    Complexity

    Time: O(n). The loop runs once for each node after the first, and each iteration does a fixed number of assignments.

    Space: O(1). The method uses three references however long the list is. A recursive solution, or one that copies values into an array, would use O(n) extra space.

    Edge cases and common mistakes

    • A single node. node is null from the start, the loop doesn't run, and the method returns the same node, whose next is null.
    • Two nodes. 1 -> 2 becomes 2 -> 1 after one iteration.
    • An empty list. This solution reads head.next first, so a null head throws a NullPointerException. The lesson's tests use lists with at least one node. To support the empty list, return null at the top when head == null.
    • Forgetting head.next = null. The old head would keep pointing at the second node, which now points back to it, and the reversed list would contain a cycle. Printing or traversing it would never finish.
    • Flipping before saving. If you write node.next = prev before saving nextNode, the following nodes are unreachable.
    • Updating in the wrong order. Setting node = nextNode before prev = node moves prev to the wrong node.
    • Returning head. After the loop the old head is the tail. The new head is prev.

    Testing

    • 1 -> 2 -> 3 -> 4 -> 5 gives 5 -> 4 -> 3 -> 2 -> 1.
    • 1 -> 2 gives 2 -> 1.
    • A single node 1 gives 1.
    • Reversing twice returns a list in the original order, as long as you use the head returned the first time.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free