Linked List - Add Two Numbers

Two non-negative integers are stored in linked lists in reverse order (ones digit first). Add the two numbers and return the sum as a linked list in the same format.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807. Digits stored reversed: 2→4→3 means 342.

Input: l1 = [0], l2 = [0]
Output: [0]

Iterate both lists simultaneously, adding digits plus carry. Create a new node for each sum digit.

Process digit by digit with carry
Create result node for each sum % 10
carry = sum / 10; continue until both lists exhausted and carry == 0

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode curr = dummy; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int sum = carry; if (l1 != null) { sum += l1.val; l1 = l1.next; } if (l2 != null) { sum += l2.val; l2 = l2.next; } carry = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; } return dummy.next; }

Complexity Analysis:

Time complexity: O(max(m,n))
Space complexity: O(max(m,n)) — result list length