Reverse Linked List
Problem Statement
Given the head of a singly linked list, reverse the
list and return the new head.
Example: Input: 1 → 2 → 3 → 4 → 5 → NULL, Output: 5 →
4 → 3 → 2 → 1 → NULL
Approach 1: Iterative
Explanation: Use three pointers: prev, curr, next.
Reverse links one by one.
Time Complexity: O(n)
Space Complexity: O(1)
prev = NULL
curr = head
while curr != NULL:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
Approach 2: Recursive
Explanation: Reverse the rest of the list recursively
and fix pointers.
Time Complexity: O(n)
Space Complexity: O(n) (recursion stack)
if head == NULL or head.next == NULL:
return head
rest = reverse(head.next)
head.next.next = head
head.next = NULL
return rest