Reverse a Linked List

Problem Statement

Given the head of a singly linked list, reverse the list and return the reversed list.

Input/Output Specifications

• Input: Head of a singly linked list
• Output: Head of the reversed linked list
• Constraints:
  • The number of nodes in the list is in the range 0, 5000
  • -5000 <= Node.val <= 5000

Examples

Example 1:

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

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Solutions

Approach 1: Iterative (Two Pointers)

This approach uses two pointers to reverse the linked list iteratively. We maintain a prev pointer to track the previous node and a current pointer to track the current node.

Algorithm:

1. Initialize prev to null and current to head
2. While current is not null:
   • Store the next node in a temporary variable
   • Reverse the link by setting current.next to prev
   • Move prev to current and current to the next node
3. Return prev as the new head

Python:

def reverseList(head):
    """
    Reverse a linked list iteratively using two pointers
    Time: O(n)
    Space: O(1)
    """
    prev = None
    current = head
    
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    
    return prev

Java:

class Solution {
    /**
     * Reverse a linked list iteratively using two pointers
     * Time: O(n)
     * Space: O(1)
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        
        return prev;
    }
}

Go:

// reverseList - Reverse a linked list iteratively using two pointers
// Time: O(n)
// Space: O(1)
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    current := head
    
    for current != nil {
        nextTemp := current.Next
        current.Next = prev
        prev = current
        current = nextTemp
    }
    
    return prev
}

JavaScript:

/**
 * Reverse a linked list iteratively using two pointers
 * Time: O(n)
 * Space: O(1)
 */
function reverseList(head) {
    let prev = null;
    let current = head;
    
    while (current !== null) {
        const nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    
    return prev;
}

C#:

public class Solution {
    /// <summary>
    /// Reverse a linked list iteratively using two pointers
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        
        return prev;
    }
}

Approach 2: Recursive

This approach uses recursion to reverse the linked list. The recursive function reverses the rest of the list and then reverses the link between the current node and the next node.

Algorithm:

1. Base case: if head is null or head.next is null, return head
2. Recursively reverse the rest of the list starting from head.next
3. Reverse the link between head and head.next
4. Return the new head of the reversed list

Python:

def reverseListRecursive(head):
    """
    Reverse a linked list recursively
    Time: O(n)
    Space: O(n) - due to recursion stack
    """
    if not head or not head.next:
        return head
    
    reversed_head = reverseListRecursive(head.next)
    head.next.next = head
    head.next = None
    
    return reversed_head

Java:

class Solution {
    /**
     * Reverse a linked list recursively
     * Time: O(n)
     * Space: O(n) - due to recursion stack
     */
    public ListNode reverseListRecursive(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode reversedHead = reverseListRecursive(head.next);
        head.next.next = head;
        head.next = null;
        
        return reversedHead;
    }
}

Go:

// reverseListRecursive - Reverse a linked list recursively
// Time: O(n)
// Space: O(n) - due to recursion stack
func reverseListRecursive(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    reversedHead := reverseListRecursive(head.Next)
    head.Next.Next = head
    head.Next = nil
    
    return reversedHead
}

JavaScript:

/**
 * Reverse a linked list recursively
 * Time: O(n)
 * Space: O(n) - due to recursion stack
 */
function reverseListRecursive(head) {
    if (head === null || head.next === null) {
        return head;
    }
    
    const reversedHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    
    return reversedHead;
}

C#:

public class Solution {
    /// <summary>
    /// Reverse a linked list recursively
    /// Time: O(n)
    /// Space: O(n) - due to recursion stack
    /// </summary>
    public ListNode ReverseListRecursive(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode reversedHead = ReverseListRecursive(head.next);
        head.next.next = head;
        head.next = null;
        
        return reversedHead;
    }
}

Key Insights

• Two-pointer technique: The iterative approach uses two pointers to traverse and reverse the list in one pass
• Recursion pattern: The recursive approach leverages the call stack to reverse the list from the end
• Link reversal: The core operation is reversing the direction of the next pointer
• Edge cases: Handle empty lists and single-node lists properly

Edge Cases

• Empty list (head is null)
• Single node list
• Two node list
• Large lists (performance consideration)

Test Cases

# Test case 1: Normal case
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
# Expected: [3,2,1]

# Test case 2: Empty list
head2 = None
# Expected: []

# Test case 3: Single node
head3 = ListNode(1)
# Expected: [1]

# Test case 4: Two nodes
head4 = ListNode(1)
head4.next = ListNode(2)
# Expected: [2,1]

Follow-up Questions

• How would you reverse a doubly linked list?
• Can you reverse only the first k nodes of a linked list?
• How would you reverse a linked list in groups of k?
• What if the linked list has a cycle?

Common Mistakes

• Forgetting to store the next node before reversing the link
• Not handling the empty list case
• Incorrectly updating pointers in the wrong order
• Memory leaks in languages that require manual memory management
• Stack overflow in recursive approach for very large lists