LeetCode 2. Add Two Numbers

Description

https://leetcode.com/problems/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 contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Explanation

The question is about performing math addition operation with two linked lists. Each node of the result linked list gets value from the sum of two input linked lists. We can just take this process as we are doing addition in columns.

Key point: We need to add a carry just as we do addition in arithmetic. A carry is a digit that is transferred from one column of digits to another column of more significant digits.

For different cases:

  • If there are remaining nodes (l1, l2) in both two linked lists, the result linked list node gets value from ((l1.val + l2.val + carry) % 10).
  • If there is only one linked list has remaining node, the esult linked list node gets value ((l1.val + carry) % 10 or (l2.val + carry) % 10).
  • If neither of linked list has remaining nodes, we should check if there is still carryover value.

Video Tutorials

Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
                
        while (l1 != null && l2 != null) {
            int value = (l1.val + l2.val + carry) % 10;
            carry = (l1.val + l2.val + carry) / 10;
            ListNode result = new ListNode(value);
            current.next = result;
            l1 = l1.next;
            l2 = l2.next;
            current = result;
        }
        
        while (l1 != null) {
            int value = (l1.val + carry) % 10;
            carry = (l1.val + carry) / 10;            
            ListNode result = new ListNode(value);
            current.next = result;
            l1 = l1.next;
            current = result;            
        }
        
        while (l2 != null) {
            int value = (l2.val + carry) % 10;
            carry = (l2.val + carry) / 10;     
            ListNode result = new ListNode(value);
            current.next = result;
            l2 = l2.next;
            current = result;            
        }        
        
        if (carry != 0) {
            ListNode result = new ListNode(carry);
            current.next = result;
            current = result;             
        }
        
        return dummy.next;        
    }
}

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        dummy = ListNode(0)
        current = dummy
        carry = 0
        while l1 != None and l2 != None:
            
            new_node_value = (l1.val + l2.val + carry) % 10
            new_node = ListNode(new_node_value)
            carry = (l1.val + l2.val + carry) // 10
            
            current.next= new_node
            current = current.next
            l1 = l1.next
            l2 = l2.next
            
            
        while l1 != None:
            
            new_node_value = (l1.val + carry) % 10
            new_node = ListNode(new_node_value)
            carry = (l1.val + carry) // 10
            
            current.next= new_node
            current = current.next
            l1 = l1.next
            
        while l2 != None:
            
            new_node_value = (l2.val + carry) % 10
            new_node = ListNode(new_node_value)
            carry = (l2.val + carry) // 10
            
            current.next= new_node
            current = current.next
            l2 = l2.next
        
        if carry != 0:
            new_node_value = (carry) % 10
            new_node = ListNode(new_node_value)
            
            current.next= new_node
            current = current.next
            
        return dummy.next

One Thought to “LeetCode 2. Add Two Numbers”

Leave a Reply

Your email address will not be published. Required fields are marked *