Reverse Linked List

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

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

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

1. 1Base case: if head is null or head.next is null, return head as the new head.
2. 2Recurse on head.next to reverse the remainder and capture the returned new head.
3. 3Set head.next.next = head so the node just ahead now points back at head.
4. 4Set head.next = null to detach head's old forward link and make it a tail.
5. 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