Add two numbers

Two non-negative integers are stored as linked lists, one digit per node, least significant digit first: 342 is 2 → 4 → 3. Return their sum as a list in the same format.

Before you code

This is grade-school addition from right to left, and the lists are already stored right to left. The lists can have different lengths, and the final carry can add a digit.

Hints

1. Use a dummy head and a tail pointer for the result, and a carry starting at 0.
2. Loop while either list has a node or carry is non-zero. Treat a missing node as 0.
3. Each step: s = a + b + carry, append a node with s % 10, set carry = s // 10.
4. [9, 9, 9] + [1] must produce four digits. That last digit comes only from the carry.

Production & complexity notes

When solving Add two numbers on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Insert, delete and the dummy head to reinforce the underlying pattern.

What it practices

Building a new list node by node behind a dummy head, from Insert, delete and the dummy head.