Problem Name: Add Two Numbers
Problem Statement:
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.
Input:
Two non-empty linked lists representing two non-negative integers.
Output:
A linked list representing the sum of the two numbers.
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.
Example:
Input: l1 = [2, 4, 3], l2 = [5, 6, 4]
Output: [7, 0, 8]
Explanation: 342 + 465 = 807.
Platforms:
Companies:
- Amazon
- Microsoft
Topics Covered:
Linked List,
Addition
Solution:
Algorithm:
1. Initialize a dummy node to form the result list and a pointer for the current position.
2. Initialize carry to 0.
3. Loop through lists l1 and l2 until you reach the end of both.
4. Set sum to carry plus the values of the nodes l1 and l2 point to (if present).
5. Update carry to sum divided by 10.
6. Create a new node with the digit value of (sum modulo 10) and set it as the next of the current node.
7. Move the pointers of l1, l2, and the current position one step forward.
8. If carry is non-zero after the loop, create a new node with carry as the value.
Code Implementation:
C:
#include <stdio.h> #include <stdlib.h> struct ListNode { int val; struct ListNode* next; }; struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* curr = dummy; int carry = 0; while (l1 != NULL || l2 != NULL) { int x = (l1 != NULL) ? l1->val : 0; int y = (l2 != NULL) ? l2->val : 0; int sum = carry + x + y; carry = sum / 10; curr->next = (struct ListNode*)malloc(sizeof(struct ListNode)); curr->next->val = sum % 10; curr = curr->next; if (l1 != NULL) l1 = l1->next; if (l2 != NULL) l2 = l2->next; } if (carry > 0) { curr->next = (struct ListNode*)malloc(sizeof(struct ListNode)); curr->next->val = carry; curr = curr->next; } curr->next = NULL; return dummy->next; }
C++:
#include <iostream> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummy = new ListNode(0); ListNode* curr = dummy; int carry = 0; while (l1 != NULL || l2 != NULL) { int x = (l1 != NULL) ? l1->val : 0; int y = (l2 != NULL) ? l2->val : 0; int sum = carry + x + y; carry = sum / 10; curr->next = new ListNode(sum % 10); curr = curr->next; if (l1 != NULL) l1 = l1->next; if (l2 != NULL) l2 = l2->next; } if (carry > 0) { curr->next = new ListNode(carry); } return dummy->next; } };
Java:
public class Solution { public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode curr = dummy; int carry = 0; while (l1 != null || l2 != null) { int x = (l1 != null) ? l1.val : 0; int y = (l2 != null) ? l2.val : 0; int sum = carry + x + y; carry = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } if (carry > 0) { curr.next = new ListNode(carry); } return dummy.next; } }
Python:
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() curr = dummy carry = 0 while l1 or l2: x = l1.val if l1 else 0 y = l2.val if l2 else 0 sum = carry + x + y carry = sum // 10 curr.next = ListNode(sum % 10) curr = curr.next if l1: l1 = l1.next if l2: l2 = l2.next if carry: curr.next = ListNode(carry) return dummy.next
Complexity Analysis:
Case | Time Complexity | Space Complexity |
---|---|---|
Worst Case | O(n) | O(n) |
Average Case | O(n) | O(n) |
Best Case | O(n) | O(n) |