Python · medium · Asked at Meta
Asked in ML Engineer interviews, in the Python round.
Iterate with prev/curr pointers, reversing next at each step.
Walk the list once, pointing each node at the one before it.
def reverse(head):
prev, curr = None, head
while curr:
nxt = curr.next # save the rest before breaking the link
curr.next = prev # point backwards
prev, curr = curr, nxt # advance
return prev # old tail is the new headO(n) time, O(1) extra space. The order of the three lines inside the loop is the whole exercise: save next first, or the rest of the list is lost the moment you rewrite curr.next. Trace it on a three-node list out loud; that is what the interviewer is waiting for.
The recursive version reverses the rest and then attaches the head at the end: new_head = reverse(head.next); head.next.next = head; head.next = None. Elegant, O(n) stack depth, so it fails on a long list in Python. Mention it, prefer the loop.
Edge cases to state without being asked: empty list, single node, and that the function returns the new head rather than mutating a caller's variable.
curr.next before overwriting it, which drops everything after the first node.