Reverse Linked List

Problem

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

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: []

Constraints:

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

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution

Approach 1: Iterative

The key insight is to iterate through the list and reverse the next pointers one by one. We maintain three pointers: previous, current, and next.

Algorithm:

Initialize prev = None, curr = head
While curr is not None:
- Save next node
- Reverse the current node’s pointer to point to prev
- Move prev and curr one step forward
Return prev (new head)

Implementation

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

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

        while curr:
            # Save next node
            next_node = curr.next
            # Reverse the pointer
            curr.next = prev
            # Move pointers forward
            prev = curr
            curr = next_node

        return prev

Approach 2: Recursive

The recursive approach reverses the rest of the list first, then fixes the current node’s pointers.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Base cases
        if not head or not head.next:
            return head

        # Reverse the rest of the list
        new_head = self.reverseList(head.next)

        # Fix pointers for current node
        head.next.next = head  # Point next node back to current
        head.next = None       # Remove forward pointer

        return new_head

Complexity Analysis

Iterative:

Time Complexity: O(n), where n is the number of nodes. We visit each node once.
Space Complexity: O(1), we only use a constant amount of extra space.

Recursive:

Time Complexity: O(n), we visit each node once.
Space Complexity: O(n) due to recursion stack depth.

Key Insights

Three Pointers Pattern: The iterative approach uses three pointers (prev, curr, next) to safely reverse pointers without losing references.
Pointer Reversal: We reverse the direction of each next pointer to point to the previous node instead of the next node.
New Head: After reversal, the last node becomes the new head. In the iterative approach, prev points to the last node when curr becomes None.
Recursive Visualization: In recursion, we first reach the end of the list, then on the way back, we reverse pointers. The last node becomes the new head and is returned up the call stack.
Edge Cases: Both approaches handle empty lists and single-node lists correctly. An empty list returns None, and a single node returns itself.