Start learning free

LESSON 302 OF 415 · LINKED LISTS

Reverse Linked List in Swift: 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 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 nil, 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 nil, 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 nil:
  • 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

    SWIFT · LINKED LISTS

    Reverse Linked List in Swift, explained

    Problem overview

    The method reverse(_ head: ListNode?) -> ListNode? receives the head of a singly linked list and returns the head of the same list in reverse order. For 1 -> 2 -> 3 -> 4 -> 5 it returns 5 -> 4 -> 3 -> 2 -> 1. The target is O(n) time and O(1) extra space, so the method can't copy the values into an array and build a new list. It has to rewire the links of the nodes it was given.

    Each node is a ListNode with an Int field val and an optional field next, of type ListNode?, which is nil at the end of the list.

    Approach: flip each link as you walk

    Reversing a list means that every arrow a -> b becomes b -> a, and that the old tail becomes the new head. The two-pointer trick used to reverse an array doesn't apply, because a singly linked list can't be walked backwards.

    The straightforward attempt is to visit a node and set node.next.next = node. It breaks as soon as it runs: after the first link is flipped, the original path forward from the next node is gone, so the walk loses the rest of the list. The remedy is to remember the next node before changing anything.

    The walk therefore uses three references:

    • prev, the node just behind the current one, which the current node's link must point to after the flip;
    • node, the node whose link is being flipped;
    • nextNode, saved from node.next before the flip, so the walk can continue.

    On 1 -> 2 -> 3, the starting state is prev = 1 and node = 2, with the head's link cut. Flipping 2 gives 2 -> 1; then prev = 2 and node = 3. Flipping 3 gives 3 -> 2 -> 1; then node is nil and prev holds 3, the new head.

    Step by step

    1. Declare prev with var and start it at head. It tracks the node before the current one.
    2. Declare node with var and start it at the second node, head!.next. The first node is handled separately. The ! force-unwraps head, which is a ListNode?, so the code assumes the list is not empty.
    3. Cut the head's link with head!.next = nil. The head becomes 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 with while node != nil.
    5. Save the rest in let nextNode = node!.next. Without this, rewriting node!.next loses every node after node. Swift doesn't treat node as non-nil inside the loop, so it needs the !.
    6. Flip the link: node!.next = prev.
    7. Advance prev: prev = node.
    8. Advance node: node = nextNode. The order of these two assignments matters: doing node = nextNode first would lose the current node before it is stored in prev.
    9. Return prev. When the loop ends, node is nil and prev is the old last node, which is the new head.

    The solution in Swift

    class Solution {
    func reverse(_ head: ListNode?) -> ListNode? {
        var prev = head
        var node = head!.next
        head!.next = nil
        while node != nil {
            let nextNode = node!.next
            node!.next = prev
            prev = node
            node = nextNode
        }
        return prev
    }
}

    Swift details worth a closer look:

    • Classes are references. ListNode is a class, so prev, node and head hold references to node objects. Setting node!.next = prev changes the node itself, and every other reference to that node sees the change. A struct would be copied instead, and the code wouldn't work.
    • Optionals and !. head and each next are optional. The ! operator unwraps one and crashes at run time if it is nil. In the loop, node! is safe because the condition just checked it.
    • node != nil. Comparing an optional with nil works even when ListNode is not Equatable, because the check asks only whether a value is present, not whether two nodes are equal.
    • Type inference. var prev = head has the type ListNode?, and var node = head!.next has the same type, so assigning prev = node and node = nextNode type-checks.
    • Memory. Swift frees a node when no reference to it remains. Reversing in place never drops a node, because each one stays reachable through prev, node or the new list.

    Complexity

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

    Space: O(1). Three references (prev, node, nextNode) are used, whatever the length of the list. No new nodes are created.

    Edge cases and common mistakes

    • One node. For 7, node starts as nil, the loop never runs, and the method returns the same node. Its next was already nil.
    • Two nodes. 1 -> 2 becomes 2 -> 1 after one pass.
    • Empty list. This version force-unwraps head in head!.next, so an empty list (nil) crashes. The lesson's tests use lists with at least one node. A safer opening is guard let head = head else { return nil }.
    • Forgetting to cut the head's link. The original head would still point at the second node, which now points back at it, a cycle that makes later traversals loop forever.
    • Not saving nextNode. After node!.next = prev, the way forward is lost, so the loop ends early or never finishes.
    • Updating the pointers in the wrong order. prev must take the current node before node moves on.
    • Returning head. The old head is now the last node, and returning it gives a list of one element.
    • After the call. The old head variable still refers to the same node, which is now the tail. Use the returned value as the new head.

    Testing

    • [1, 2, 3, 4, 5] gives [5, 4, 3, 2, 1].
    • [1, 2] gives [2, 1].
    • [7] gives [7].
    • [1, 2, 3] gives [3, 2, 1], and the old head node (value 1) is now the tail, so walking from it gives just [1].
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free