DEV Community

Hector Williams
Hector Williams

Posted on

Leetcode #2.Add Two Numbers

Problem
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.

Algorithmic Solution
As a prerequisite to solve this problem, you create and maintain 4 ListNode pointers: one pointer each for each linked list (l1Current,l2Current)another for the result ListNode(result) and one to keep track of the current result(resultCurrent).l1Current is initialized to l1,l2Current to l2,result and resultCurrent to null. You also keep a variable to keep track of a carryover digit called carryover that is initially 0 and will be 1 if the sum of 2 node values is greater than 10 and 0 otherwise.
We then use a while loop, that runs whilst both of the pointers to the ListNodes are not null. This traverses all the nodes. On each traversal, we get the values of both current ListNodes, add them and the carryover. If the resultant value is greater than or equal to 10,we set the carryover to 1 otherwise we set it to 0.We add the resulting node to the result ListNode and move the resultCurrent node to this. Once we reach a null value for either l1Current or l2Current,we repeat the while loop separately for both l1 and l2 until both l1Current and l2Current are null adding the values of the list to the carryover , adding new nodes to result and updating resultCurrent. If at the end of this, if the value of carryover _is 1,we add a node with value 1 to the _result. Below is the code. Feel free to like, share and comment.

/**
 * 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 l1Current=l1;
      ListNode l2Current=l2;
      ListNode result= null;ListNode resultCurrent=null;   
      int carryover=0;  
      while(l1Current!=null && l2Current!=null){
       int l1Value=l1Current.val;
       int l2Value=l2Current.val;
       int resultVal=l1Value+l2Value+carryover;
       if(resultVal>=10){
        resultVal=resultVal-10;
        carryover=1;
       }else carryover=0;
       if(result==null){
        result=new ListNode(resultVal);
        resultCurrent=result;
       }else{
        ListNode tmp=new ListNode(resultVal);
        resultCurrent.next=tmp;
        resultCurrent=resultCurrent.next;
       } 
       l1Current=l1Current.next;
       l2Current=l2Current.next;
      }
      while(l1Current!=null){
       int resultVal=carryover+l1Current.val;
       if(resultVal>=10){
        carryover=1;
        resultVal-=10;
       }else carryover=0;
       ListNode tmp=new ListNode(resultVal);
       resultCurrent.next=tmp;
       resultCurrent=resultCurrent.next;
       l1Current=l1Current.next;
      }   
       while(l2Current!=null){
       int resultVal=carryover+l2Current.val;
       if(resultVal>=10){
        carryover=1;
        resultVal-=10;
       }else carryover=0;
       ListNode tmp=new ListNode(resultVal);
       resultCurrent.next=tmp;
       resultCurrent=resultCurrent.next;
       l2Current=l2Current.next;
      } 
      if(carryover==1){
        ListNode tmp=new ListNode(1);
        resultCurrent.next=tmp;
      }
      return result;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)