Reversing a Singly Linked List

Problem Description

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

Naive Approach

A naive approach to reversing a singly linked list involves creating a new linked list by iterating through the original list and adding each element to the beginning of the new list. This effectively reverses the order of the elements.

Code (Python)

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

def reverseListNaive(head):
    new_head = None
    current = head
    while current:
        new_node = ListNode(current.val)
        new_node.next = new_head
        new_head = new_node
        current = current.next
    return new_head

Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list, as we iterate through each node once.
• Space Complexity: O(n), as we create a new linked list with n nodes.

Optimal Approach: Iterative In-Place Reversal

The optimal approach reverses the linked list in-place, meaning without using extra space proportional to the input size. This can be done iteratively by changing the next pointers of each node.

Algorithm

1. Initialize prev to None and current to head.
2. Iterate through the list. In each iteration:
   • Store the next node in next_node.
   • Reverse the next pointer of the current node to point to prev.
   • Move prev to current and current to next_node.
3. After the loop finishes, prev will be the new head of the reversed list.

Code (Python)

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

def reverseList(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list, as we iterate through each node once.
• Space Complexity: O(1), as we only use a constant amount of extra space for pointers.

Recursive Approach

Another optimal approach is using recursion.

Algorithm

1. Base case: If the list is empty or has only one node, it's already reversed.
2. Recursively reverse the rest of the list.
3. Adjust the pointers to make the current head the new tail.

Code (Python)

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

def reverseListRecursive(head):
    if not head or not head.next:
        return head
    
    new_head = reverseListRecursive(head.next)
    head.next.next = head
    head.next = None
    
    return new_head

Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list.
• Space Complexity: O(n) due to the recursive call stack.

Edge Cases

• Empty List: If the input list is empty (head is None), the function should return None.
• Single Node List: If the list contains only one node, the function should return the node itself as it is already reversed.

Summary

The optimal approach for reversing a singly linked list is the iterative in-place reversal, which has a time complexity of O(n) and a space complexity of O(1). The recursive approach also has a time complexity of O(n) but uses O(n) space due to the call stack. The naive approach uses O(n) time and O(n) space. It's crucial to handle edge cases such as an empty list or a single-node list correctly.