[Interview] 4. Reversing a Singly Linked List

In this code, we maintain two pointers, p1 and p2. The p1 pointer traverses the list, while p2 reverses the direction of the pointers. Initially, we set the head's next pointer to NULL, effectively marking the end of the reversed list. As we iterate through the list, we update the pointers until all nodes are reversed.

Method 2: Using a Stack

The second method leverages the Last-In, First-Out (LIFO) property of a stack to reverse the linked list. This method is also O(n) in time complexity but requires O(n) space for the stack. Here’s how this method is implemented: