Reverse a Linked List

To reverse a singly linked list efficiently, I would use an iterative approach with constant space complexity. First, I need to handle edge cases where the head is null or contains only one node, returning it immediately as no reversal is needed. For the general case, I will maintain three pointers: previous, current, and next. Initially, previous is set to null, and current points to the head. In each iteration, I save the next node to avoid losing the rest of the list. Then, I reverse the link by setting current.next to previous. After updating the links, I advance both previous and current one step forward. This process repeats until current becomes null, meaning we have reached the end of the original list. At this point, previous will be pointing to the new head of the reversed list. For example, reversing 1->2->3 starts with prev=null, curr=1. We save next=2, set 1.next to null, move prev to 1 and curr to 2. Next, we save next=3, set 2.next to 1, move prev to 2 and curr to 3. Finally, 3.next becomes 2, and we return 3 as the new head. This ensures we traverse the list exactly once, achieving O(n) time complexity while using only O(1) extra space, which aligns well with Google's emphasis on resource efficiency and clean code.