The recursive approach reverses the rest of the list first, then fixes the current node:
def reverse(head):
if head == null or head.next == null:
return head
newHead = reverse(head.next)
head.next.next = head
head.next = null
return newHead
The insight: after reverse(head.next) returns, head.next still points to what was the second node. That node is now the tail of the reversed suffix. So head.next.next = head appends head to the end.
Time: . Space: for the call stack.
The iterative version is more space-efficient, but the recursive version is cleaner to write.