The Plus One Linked List problem gives a non-negative integer as a singly linked list (most significant digit first) and asks you to add 1. Carry propagation goes from the tail to the head, which is reversed from the list's direction. This coding problem uses recursion or two-pointer reversal. The linked list and math interview pattern is the core.
Amazon and Google ask this because adding 1 to a linked list requires traversing to the end and propagating carry backwards — either using recursion (natural backtracking) or by reversing the list, incrementing, and reversing back.
Recursion (implicit stack for carry). Recursive approach: traverse to the tail, add 1 to the last node, propagate carry back up the recursion stack. Return carry at each level: if node.val + carry > 9, set to 0, return carry=1; else set to node.val + carry, return carry=0. If carry remains at the head, prepend a new node with value 1.
List: 9→9→9. Process recursively from tail:
Linked list arithmetic problems traverse to the tail either recursively (using the call stack) or by reversing. The recursive approach is elegant: return a carry value up the call stack. The reverse-and-reverse approach works for longer lists where recursion depth could be an issue. Practice both: "add two linked lists," "multiply linked lists," "subtract linked lists." Recursion for carry is the cleanest approach for single-list addition.
