Start learning free

LESSON 277 OF 348 · LINKED LISTS

Reverse Linked List in TypeScript: O(n) Time, 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 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
    Ctrl + Enter to check

    TYPESCRIPT · LINKED LISTS

    Reverse Linked List in TypeScript, explained

    Problem overview

    The method reverse receives the head of a singly linked list, a ListNode | null, and returns the head of the reversed list. Each node has a val and a next link to the following node, and the last node's next is null.

    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 an array and rebuild the list. It has to rewire the existing nodes.

    Approach: flip every link

    Reversing a list means turning each arrow around. In 1 -> 2 -> 3 the links become 1 <- 2 <- 3, and the old tail, 3, is the new head. The old head, 1, becomes the tail, so its next must become null.

    A first attempt walks forward with a variable node and sets node.next.next = node at each step. It fails, because the moment a link is flipped you lose access to the rest of the list. At node 1, flipping the link between 1 and 2 leaves 2 pointing back at 1, and the old link from 2 to 3 is gone. The walk can't continue.

    The fix is to keep three references while walking:

    • prev, the node before the current one, which is where the flipped link will point;
    • node, the node whose link is being flipped;
    • nextNode, the node after node, saved before the link changes so nothing is lost.

    Each pass through the loop flips one link and moves all three references one node forward. When node runs off the end, prev is the last node of the original list, which is the head of the reversed one.

    On 1 -> 2 -> 3: set prev to 1, node to 2 and cut the first node's link, so the list is 1 and 2 -> 3. First pass: save 3, point 2 back at 1, move on, so prev is 2 and node is 3. Second pass: save null, point 3 at 2, so prev is 3 and node is null. The loop ends and the method returns 3, the head of 3 -> 2 -> 1.

    Step by step

    1. Declare prev with let, typed ListNode | null, and start it at head. It tracks the node before the current one.
    2. Declare node the same way and start it at the second node, head!.next. The ! is a non-null assertion: head is typed ListNode | null, but the lesson's lists are never empty.
    3. Cut the head's link with head!.next = null. The head will be the last node 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 of the list in nextNode (node.next) before changing any link.
    6. Flip the link: node.next = prev.
    7. Move prev forward to node.
    8. Move node forward to nextNode. The order of these two assignments matters: updating node first would lose the current node before prev had recorded it.
    9. Return prev, the new head.

    The solution in TypeScript

    class Solution {
    reverse(head: ListNode | null): ListNode | null {
        let prev: ListNode | null = head;
        let node: ListNode | null = head!.next;
        head!.next = null;
        while (node !== null) {
            let nextNode: ListNode | null = node.next;
            node.next = prev;
            prev = node;
            node = nextNode;
        }
        return prev;
    }
}

    The TypeScript details worth a closer look:

    • The non-null assertion !. head!.next tells the compiler to treat head as non-null. It changes nothing at run time. If head is actually null, the line throws a TypeError ("Cannot read properties of null"). The assertion is a promise by the programmer, not a check.
    • Union types. ListNode | null says a variable holds a node or null. With strict null checks on, the test node !== null in the loop would narrow the type so that node.next is allowed. The lessons compile with strict off, where null is accepted everywhere, so the annotation documents the intent rather than enforcing it.
    • References, not copies. Variables hold references to node objects. prev = node makes both names point at the same node, and node.next = prev changes the stored link in that object. The nodes themselves never move or get copied.
    • Annotations are erased. At run time only the object links exist; the type annotations are removed when TypeScript compiles to JavaScript.

    Complexity

    Time: O(n). The loop runs once per node after the first, doing a fixed number of assignments each time.

    Space: O(1). Three variables, prev, node and nextNode, are all the extra memory, however long the list is. The links are rewired in place, and there is no recursion that would add stack depth.

    Edge cases and common mistakes

    • One node. For [1], node starts as null, the loop doesn't run and the method returns the same node, whose next is null.
    • Two nodes. For [1, 2], one pass flips the single link, and the result is [2, 1].
    • An empty list. This solution fails on null, because head!.next reads a property of null. The lesson's tests don't use an empty list. To handle one, add if (head === null) return null; at the top.
    • Not saving the next node. Changing node.next without keeping the old value loses the rest of the list. Walking the list afterwards ends in the wrong place.
    • Forgetting to cut the head. Without head!.next = null, the old head and the second node point at each other. The returned list contains a cycle, and any code that walks it until null never finishes.
    • Swapping the last two assignments. If node = nextNode ran before prev = node, prev would end up pointing at the next node and the links would be wrong.
    • Returning head. After the reversal, the original 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].
    • [1] gives [1].
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free