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

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

💡 Think: Flip each pointer with prev–curr–next until the end, returning the last seen node.

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

💡 Think: Reverse the rest first, then point head.next back to head and cut head.next.