Reverse a Linked List: Step-by-Step Visual Guide

The Core Problem

Given the head of a singly linked list, our goal is to reverse the list, turning the elements backward so that the tail becomes the new head, and return the pointer to the new head node.

For example:

• Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
• Output: null <- 1 <- 2 <- 3 <- 4 <- 5 (or 5 -> 4 -> 3 -> 2 -> 1 -> null)

Interactive Visualization

Click through our interactive animation to see how pointers get reassigned node-by-node. Notice how the pointers prev, curr, and nextTemp move in tandem.

The Iterative Approach

To reverse a list iteratively, we traverse the list exactly once. As we visit each node, we change its next pointer to point to its predecessor instead of its successor.

Because a node's next pointer is overwritten, we must store the subsequent node in a temporary variable (nextTemp) before changing the link, so we do not lose track of the remaining list.

Pointers Explained:

1. curr: The node we are currently visiting (starts at head).
2. prev: The node preceding curr (starts at null, since the original head will become the new tail pointing to null).
3. nextTemp: Holds reference to the next node (curr.next) before we sever the link.

Step-by-Step Loop Logic:

• Save next node: nextTemp = curr.next
• Reverse link: curr.next = prev
• Move prev pointer forward: prev = curr
• Move curr pointer forward: curr = nextTemp

Code Implementations

Here is the clean implementation of Linked List Reversal:

JavaScript / TypeScript (Iterative)

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val: number) {
        this.val = val;
        this.next = null;
    }
}

function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let curr: ListNode | null = head;

    while (curr !== null) {
        let nextTemp: ListNode | null = curr.next; // Save next node
        curr.next = prev;                         // Reverse connection
        prev = curr;                              // Move prev forward
        curr = nextTemp;                          // Move curr forward
    }

    return prev; // prev will point to the new head
}

Python (Iterative)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    prev = None
    curr = head
    
    while curr:
        next_temp = curr.next  # Save next
        curr.next = prev       # Reverse link
        prev = curr            # Move prev
        curr = next_temp       # Move curr
        
    return prev

Java (Iterative)

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode nextTemp = curr.next; // Save next
            curr.next = prev;             // Reverse link
            prev = curr;                  // Move prev
            curr = nextTemp;              // Move curr
        }
        
        return prev;
    }
}

The Recursive Approach

Alternatively, we can reverse the list recursively. The recursive version traverses down to the end of the list first, and then reverses the pointer connections as the recursive calls pop off the call stack.

Recursive Implementation (Python)

def reverseListRecursive(head: ListNode) -> ListNode:
    # Base cases: empty list or single node
    if not head or not head.next:
        return head
        
    # Reverse the rest of the list
    new_head = reverseListRecursive(head.next)
    
    # Put head at the end of the reversed list
    head.next.next = head
    head.next = None
    
    return new_head

Complexity Analysis

Iterative Method:

• Time Complexity: O(N), where N is the number of nodes in the list. We visit each node exactly once.
• Space Complexity: O(1). Only three pointers are used.

Recursive Method:

• Time Complexity: O(N). We visit each node.
• Space Complexity: O(N). Due to the call stack depth from recursive executions.

Summary

1. Reversing a list iteratively is highly recommended in coding interviews because of its O(1) constant space footprint.
2. Always ensure you keep a pointer reference to the next node before modifying the current node's pointer.

Stay sharp for coding assessments and final exams! Use our free academic tools, including the GPA to Percentage Calculator, to check your academic stats and keep your records in order.