Reversal

Reversing a linked list is a fundamental manipulation task and a very common interview question. It can be solved using two primary approaches: iterative and recursive. The iterative approach is generally more space-efficient. It involves traversing the list while keeping track of three pointers: `previous`, `current`, and `next`. We initialize `previous` to null and `current` to the head. In each step of the loop, we first store the link to the next node (`next = current->next`). Then, we reverse the pointer of the `current` node to point to `previous` (`current->next = previous`). Finally, we move our `previous` and `current` pointers one step forward for the next iteration (`previous = current` and `current = next`). When the loop finishes, `previous` will be pointing to the new head of the reversed list. The recursive approach provides a more concise, albeit less intuitive, solution. The recursive function `reverse(node)` will reverse the rest of the list starting from `node->next` and then attach the current `node` to the end of that reversed list. The base case is when the list is empty or has only one node. While elegant, recursion uses stack space, leading to O(n) space complexity, whereas the iterative solution uses O(1) space.