Reverse Linked List - Video Solutions

Problem Overview: Reverse a singly linked list so the tail becomes the new head and every node points to its previous node. You receive the head of the list and must return the new head after reversing all pointers.

Linked lists differ from arrays because nodes are connected by references instead of indices. Reversing the list means walking through each node and redirecting its next pointer. The challenge is doing this without losing access to the remaining nodes while you modify the links. This problem is a core exercise for mastering linked list pointer manipulation.

Approach 1: Iterative Pointer Reversal (O(n) time, O(1) space)

The iterative solution walks through the list once while reversing the direction of every pointer. Maintain three variables: prev, curr, and next. Start with prev = null and curr = head. For each node, temporarily store curr.next in next, set curr.next = prev to reverse the pointer, then advance both pointers forward. This continues until curr becomes null. The last non-null node stored in prev becomes the new head.

The key insight is preserving the next node before modifying the pointer. Without that temporary variable, the rest of the list would be lost. This approach processes each node exactly once, giving O(n) time complexity with O(1) extra space. Most production code uses this version because it is efficient and avoids recursion overhead.

Approach 2: Recursive Reversal (O(n) time, O(n) space)

The recursive method reverses the list from the second node onward, then fixes the first node afterward. Call the function recursively with head.next until reaching the last node, which becomes the new head of the reversed list. During the stack unwind phase, redirect pointers so head.next.next = head and set head.next = null to break the original link.

This approach expresses the reversal elegantly using recursion. Each call handles one node and relies on the rest of the list already being reversed by deeper calls. The algorithm still visits every node once, so time complexity remains O(n). However, the recursion stack stores up to n calls, giving O(n) space complexity. The concept relies on understanding the call stack and is closely related to problems involving recursion.

Recommended for interviews: Interviewers typically expect the iterative solution first because it demonstrates strong control of pointer manipulation and uses constant extra space. Showing the recursive version afterward proves deeper understanding of how linked list operations can be expressed using recursion. Both run in O(n) time, but the iterative approach is usually considered the optimal production implementation.