Reverse Linked List
Candidates have reported being asked to reverse a linked list at Amazon, Microsoft, and ByteDance. We'll work with a singly linked list, where each node has a next reference. We need to reverse those references in place and return the new head while keeping the existing nodes and values.
In a doubly linked list, we would swap each node's next and previous references and update the head.
Before changing a link, we need to keep a reference to the next node so that we can continue through the list afterward.
Save the next node first
We use three pointers. We keep the head of the reversed portion in prev, the node we're processing in current, and its original next node in following before we change the link.
Start with prev = None and current = head. Save current.next in following, then point current.next at prev.
After reversing the link at node 14, move prev to 14 and current to the saved node 22. Repeat the same save, reverse, and advance sequence until current is null, then return prev as the new head.
def reverse_list(head):
prev = None
current = head
while current is not None:
following = current.next
current.next = prev
prev = current
current = following
return prevRetain the returned head in the caller with head = reverse_list(head). We visit each of the n nodes once, taking O(n) time and O(1) extra space. With a conventional recursive reversal, we use O(n) call-stack space, so we use iteration for the constant-space requirement.