EasyLinked ListRecursion

Reverse Linked List

2 approaches, code in every language

You are given the head of a singly linked list. Your job is to flip the direction of every link so that the node that used to be last becomes the new front of the list.

After the reversal, return a reference to the head of the rearranged list. The values stored in the nodes stay the same; only the connections between nodes change.

Example 1

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

Output: [5,4,3,2,1]

Each next-pointer is redirected backward, so traversal now starts at 5 and ends at 1.

Example 2

Input: head = [1,2]

Output: [2,1]

The two nodes swap roles: 2 becomes the head and 1 becomes the tail.

Constraints

The number of nodes is in the range [0, 5000].
-5000 <= Node.val <= 5000

Iterative Pointer Reversal

Sweep the list once, flipping each node's next pointer to point at the node behind it.

Loading animation…

Intuition

Reversing a list is really just re-aiming every next pointer at the previous node instead of the following one. If we keep track of the node we already reversed (prev) and the node we are about to reverse (curr), we can rewire one link at a time. The only danger is losing the rest of the list the moment we overwrite curr.next, so we stash it first. Walking left to right, prev trails one step behind curr and eventually lands on the original tail. When curr falls off the end, prev is the new head.

Algorithm walkthrough

1Initialize prev to null and curr to head.
2Save the next node in a temporary variable so the link forward is not lost.
3Redirect curr.next to point back at prev.
4Advance prev to curr and curr to the saved next node.
5Repeat until curr becomes null; prev now references the reversed list's head.
6Return prev.

Implementation

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

Time

O(n)

Space

O(1)

Every node is visited exactly once and only a constant number of pointers is used.

Recursive Reversal

Recurse to the tail, then rewire pointers on the way back up so each node points to its predecessor.

Loading animation…

Intuition

Think of the reversal as: reverse everything after the head, then splice the head onto the very end. The recursion dives all the way to the last node, which becomes the new head and is passed back unchanged through every stack frame. On the way back, each frame holds a node whose successor has already been reversed. That successor's next pointer is bent back onto the current node, and the current node's forward link is cleared so it becomes a tail. This unwinding rebuilds the list in reverse order.

Algorithm walkthrough

1Base case: if head is null or head.next is null, return head as the new head.
2Recurse on head.next to reverse the remainder and capture the returned new head.
3Set head.next.next = head so the node just ahead now points back at head.
4Set head.next = null to detach head's old forward link and make it a tail.
5Return the unchanged new head up the call stack.

Implementation

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        newHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return newHead

Time

O(n)

Space

O(n)

The recursion depth equals the number of nodes, so the call stack uses linear extra space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Rewind the Telemetry Chain is our own problem on the technique behind Reverse Linked List: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free

Reverse Linked List

Problem description

Example 1

Example 2

Constraints

Create a free account to see the solution

Now solve one you haven't seen.