Skip to content

LeetCode: 2-Add Two Numbers Solution

Last Updated on 2022-09-19 by Clay

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:

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


In this problem, we will get the two linked-list data structure, and then we will sum their value and return the linked-list result.


Solution

In the first try, I build the third linked list and store the sum value of two linked list value. It seems fairly intuitive at first glance, but the actual running results show that I use more memory than others.

After thinking about if, I finally thought of using only one linked list to add the value of the other linked list, and confirming the carry at any time. So that I do not have to access a third linked list.

In this case, it is divided into three situations (assume I store the sum value into L1):

  • L1 ends first: directly point next to the remaining links of L2, and return the result
  • L2 ends first: directly return the L1 result
  • L1 and L2 end at the same time: also return result directly


C++ Sample Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // Init
        ListNode *currentNode = new ListNode(0, l1);
        
        
        // Traverse
        while (true) {
            // Sum
            currentNode->next->val += l2->val;
            
            // Carry
            if (currentNode->next->val >= 10) {
                currentNode->next->val %= 10;

                if (currentNode->next->next != NULL) {
                    ++currentNode->next->next->val;
                }
                else {
                    ListNode *newNode = new ListNode(1);
                    currentNode->next->next = newNode;
                    currentNode->next->val %= 10;
                }
            }

            // Check
            if (currentNode->next->next == NULL && l2->next == NULL) {
                break;
            }
            else if (currentNode->next->next != NULL && l2->next == NULL) {
                l2->next = new ListNode(0, NULL);
            }
            else if (currentNode->next->next == NULL && l2->next != NULL) {
                currentNode->next->next = l2->next;
                break;
            }
            
            // Forward
            currentNode->next = currentNode->next->next;
            l2 = l2->next;
        }
        
        return l1;
    }
};




Python Sample Code

# 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:
        current = ListNode()
        current.next = l1
        
        while True:
            current.next.val += l2.val
            
            # Carry
            if current.next.val >= 10 and current.next.next != None:
                current.next.val -= 10
                current.next.next.val += 1
            elif current.next.val >= 10 and current.next.next == None:
                current.next.val -= 10
                current.next.next = ListNode(1);
            
            # Forward
            if current.next.next != None:
                current.next = current.next.next
            else:
                current.next.next = l2.next;
                current.next = current.next.next
                l2.next = None;
                
            if l2.next != None:
                l2 = l2.next
            else:
                l2.val = 0
            
            if current.next == None and l2.next == None:
                break
        
        return l1


References


Read More

Leave a Reply