Skip to content
AI360Xpert
Back to Linked List
Medium

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Examples

Input:l1 = [2,4,3], l2 = [5,6,4]
Output:[7,0,8]
342 + 465 = 807.
Input:l1 = [0], l2 = [0]
Output:[0]

Constraints

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Math & Carry (Optimal)

Approach

Initialize a dummy node and a tail pointer. Maintain a `carry` variable (initially 0). Iterate while either list has nodes left, or there is a non-zero carry. In each iteration, get the values from the lists (or 0 if a list is exhausted), add them along with the carry. The new carry is `sum / 10`, and the digit for the new node is `sum % 10`. Attach the new node to the tail.

Complexity Analysis

Time Complexity
O(max(n, m))
Space Complexity
O(max(n, m))

Space complexity is proportional to the length of the result list, which is at most max(n,m) + 1.

Solution.java
class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        ListNode dummy = new ListNode(0);        ListNode tail = dummy;        int carry = 0;                while (l1 != null || l2 != null || carry != 0) {            int v1 = (l1 != null) ? l1.val : 0;            int v2 = (l2 != null) ? l2.val : 0;                        // Calculate sum and carry            int sum = v1 + v2 + carry;            carry = sum / 10;            int digit = sum % 10;                        // Add new node to result            tail.next = new ListNode(digit);                        // Update pointers            tail = tail.next;            if (l1 != null) l1 = l1.next;            if (l2 != null) l2 = l2.next;        }                return dummy.next;    }}