Reverse Linked List

206.Reverse Linked List

Linked List

Recursion

Problem Statement:

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]

Algorithm:

1. Iterative Approach:
   • Track three pointers: prev, curr, and next
   • Save next node before changing pointer
   • Point current to previous node
   • Move prev and curr forward
2. Recursive Approach:
   • Base case: null node returns prev
   • Save next pointer before modifying
   • Point current to previous node
   • Recurse with node becoming prev and next becoming node

Complexity:

Time: O(n) | Space: O(1) iterative, O(n) recursive

Java Solution:

// Iterative solution
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    
    while(curr != null) {
        ListNode next = curr.next;  // Save next node
        curr.next = prev;          // Reverse pointer
        prev = curr;               // Move prev forward
        curr = next;               // Move curr forward
    }
    
    return prev;
}

// Recursive solution
public ListNode reverseList(ListNode head) {
    return reverseList(null, head);
}

public ListNode reverseList(ListNode prev, ListNode node) {
    if (node == null) return prev;
    
    ListNode next = node.next;    // Save next node
    node.next = prev;            // Reverse pointer
    
    return reverseList(node, next);
}

Python Solution:

# Iterative solution
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    curr = head
    
    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    
    return prev

# Recursive solution
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    def reverse(prev, node):
        if not node:
            return prev
            
        next = node.next
        node.next = prev
        return reverse(node, next)
        
    return reverse(None, head)

C++ Solution:

// Iterative solution
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

// Recursive solution
ListNode* reverseList(ListNode* head) {
    return reverseListHelper(nullptr, head);
}

ListNode* reverseListHelper(ListNode* prev, ListNode* node) {
    if (!node) return prev;
    
    ListNode* next = node->next;
    node->next = prev;
    return reverseListHelper(node, next);
}