Add Two Numbers - LeetCode Solution and Approach

 

 2. Add Two Numbers  - LeetCode - Medium

Solve this problem in LeetCode

Problem Description:

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. 

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [7,0,8]

Explanation: 342 + 465 = 807.

Example 2:

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

Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

Output: [8,9,9,9,0,0,0,1]

 

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.

Approach:

As digits are stored in reverse order in Linked List. We will iterate through the both at same time and get the current Digits. We can now easily add the digits and store the carry if any. We will add the sum of current Digits to answer and keep iterating.

JAVA:

Time Complexity : 0(n)

Space Complexity: 0(n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode sum = new ListNode();
        ListNode header = sum; //storing Header
        int carry = 0, t = 0;
        while (l1 != null || l2 != null || carry != 0) {
            // calculating sum of current Digits and storing in t
            if (l1 != null && l2 != null) t = l1.val + l2.val + carry;
            else if (l1 == null && l2 != null) t = l2.val + carry; // not taking l1 if null
            else if (l2 == null && l1 != null) t = l1.val + carry; // not taking l2 if null
            else if (l1 == null && l2 == null) t = carry; // not taking l1 and l2 if null
            carry = t / 10; // calculating carry from t
            if (l1 != null) l1 = l1.next; // iterating through linkedlist 1
            if (l2 != null) l2 = l2.next; // iterating through linkedlist 2
            sum.next = new ListNode(t % 10); // storing last digit of sum of current digits to LinkedList
            sum = sum.next;
        }
        return header.next;
    }
}

Keep Learning and Practicing with Programming Chaska !!!