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