Start learning free

LESSON 271 OF 338 · LINKED LISTS

Reverse Linked List in Go: 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 8
    Ctrl + Enter to check

    GO · LINKED LISTS

    Reverse Linked List in Go, explained

    Problem overview

    The function reverseList receives head, the first node of a singly linked list, and returns the head of the same list with every link turned around. Each *ListNode has a Val and a Next pointer. For [1, 2, 3, 4, 5] the result is [5, 4, 3, 2, 1]: the old last node becomes the head, and the old head becomes the tail, whose Next is nil.

    The statement asks for O(n) time and O(1) extra space. So the function can't copy the values into a slice and rebuild the list. It has to rewire the nodes that already exist.

    Approach: flip one link at a time

    A singly linked list only points forward, so a node can't find the node before it. Reversing means making each node point at its predecessor instead of its successor. Walk the list from the front and, at each node, flip its single outgoing link.

    There is one trap. The moment current.Next is overwritten, the rest of the list is no longer reachable from current. Take 1 -> 2 -> 3: if the link of node 1 is pointed backwards before anything is saved, nodes 2 and 3 are lost from node 1's point of view. So the walk keeps three pieces of information:

    • previous, the node that has already been reversed and sits just behind current;
    • current, the node whose link is flipped now;
    • next, a saved copy of current.Next, taken before the link changes.

    On [1, 2, 3] the state evolves like this:

    1. Start: previous is nil, current is node 1. Save next = node 2, point node 1 at nil, then move on: previous = node 1, current = node 2.
    2. Save next = node 3, point node 2 at node 1, move on: previous = node 2, current = node 3.
    3. Save next = nil, point node 3 at node 2, move on: previous = node 3, current = nil.

    The loop stops and previous, node 3, is the head of 3 -> 2 -> 1.

    Step by step

    1. Declare previous as a typed nil. The first node of the reversed list must end up pointing at nothing, so previous starts as nil. Go can't infer a type from a bare nil, so previous := nil fails with the compile error use of untyped nil in assignment. The conversion (*ListNode)(nil) gives the variable the type *ListNode.
    2. Declare current and set it to head. This is the node being processed.
    3. Loop while current != nil. Go has no while; a for with only a condition does the same job.
    4. Save current.Next in next before touching any link, so the rest of the list stays reachable.
    5. Reverse the link: current.Next = previous. For the first node this sets Next to nil, which is exactly what the new tail needs.
    6. Advance previous to current. Do this before moving current, otherwise the reference to the node just reversed is lost.
    7. Advance current to the saved next.
    8. Return previous. When the loop ends, current is nil and previous holds the last node that was reversed, the new head.

    The solution in Go

    func reverseList(head *ListNode) *ListNode {
	previous := (*ListNode)(nil)
	current := head
	for current != nil {
		next := current.Next
		current.Next = previous
		previous = current
		current = next
	}
	return previous
}

    Go details worth knowing:

    • Pointers are copied, nodes are not. current := head copies the pointer, so moving current never changes the caller's head variable. The nodes themselves are shared, which is why writing to current.Next changes the caller's list.
    • Field access through a pointer uses a plain dot. current.Next works on a *ListNode without any -> or explicit dereference.
    • next is a fine variable name. Go has no next keyword, so the name doesn't collide with anything.
    • Unused variables are errors. Every variable declared with := here is used, which the compiler requires.

    Complexity

    Time: O(n). The loop visits each node once and does a fixed number of pointer assignments per node.

    Space: O(1). Only the three pointers previous, current and next are stored. No new nodes are allocated; the existing ones are relinked.

    Edge cases and common mistakes

    • Empty list. With head == nil the loop never runs and the function returns previous, which is nil. No special case is needed.
    • One node. The loop runs once: the node's Next is set to nil (it already was) and the node is returned. [7] stays [7].
    • Not saving next. Writing current.Next = previous and then trying to continue with current.Next walks backwards into the part already reversed, so the rest of the list is never reached.
    • Wrong update order. Setting current = next before previous = current makes previous point at the node that comes next instead of the one just reversed, so a link is lost.
    • Returning head. After the reversal the original head is the tail, with Next == nil. Returning it gives a one-element list.

    Testing

    • [1, 2, 3, 4, 5] gives [5, 4, 3, 2, 1].
    • [7] gives [7].
    • [] (a nil head) gives [].
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free