LeetCode Question Add Two Numbers Solution

Introduction

Leetcode's "Add Two Numbers" is a popular algorithm problem that involves manipulating linked lists to simulate the addition of two non-negative integers. The problem is both challenging and educational, as it touches upon several important computer science concepts such as linked list manipulation, handling carry-over during addition, and basic arithmetic operations.

In this blog post, we'll walk through the problem description, explore an example to understand the requirements, discuss constraints, provide a detailed explanation of the approach, and finally, present solutions in multiple programming languages: C/C++, Java, Python, and JavaScript.

Add Two Numbers Solution

Problem Description

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

Let's consider the following example to understand the problem:

Input

l1 = [2, 4, 3]
l2 = [5, 6, 4]

Output:

[7, 0, 8]

342 (which is 2 -> 4 -> 3 in reverse order)
465 (which is 5 -> 6 -> 4 in reverse order)
Sum: 807 (which is 7 -> 0 -> 8 in reverse order)

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.

To solve this problem, we need to traverse both linked lists node by node, adding the corresponding digits along with any carry from the previous addition. If the sum of two digits exceeds 9, we need to carry the extra value to the next addition. Here is the step-by-step process:

Explanation

Initialize a dummy node to help easily return the result list.

Use a pointer to traverse the result list and carry to store any carry-over.

Traverse both linked lists simultaneously, adding corresponding digits along with the carry.

If the sum of two digits (plus carry) is 10 or more, set carry to 1, and the current digit to sum % 10.

Move to the next nodes in both lists (if available).

After the loop, if there's any carry left, add a new node with carry value.

Return the next node of the dummy node as the head of the result list.

Code Solutions

C/C++ Code

#include <iostream>

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* p = l1, *q = l2, *curr = dummy;
int carry = 0;
while (p != NULL || q != NULL) {
int x = (p != NULL) ? p->val : 0;
int y = (q != NULL) ? q->val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr->next = new ListNode(sum % 10);
curr = curr->next;
if (p != NULL) p = p->next;
if (q != NULL) q = q->next;
}
if (carry > 0) {
curr->next = new ListNode(carry);
}
return dummy->next;
}
}; {codeBox}

Java Code

public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode p = l1, q = l2, curr = dummy;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummy.next;
}
} {codeBox}

Python Code

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()
current, carry = dummy, 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
current.next = ListNode(sum % 10)
current = current.next
if l1: l1 = l1.next
if l2: l2 = l2.next
if carry > 0:
current.next = ListNode(carry)
return dummy.next {codeBox}

JavaScript Code

function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}

var addTwoNumbers = function(l1, l2) {
let dummy = new ListNode(0);
let p = l1, q = l2, curr = dummy;
let carry = 0;
while (p !== null || q !== null) {
let x = (p !== null) ? p.val : 0;
let y = (q !== null) ? q.val : 0;
let sum = carry + x + y;
carry = Math.floor(sum / 10);
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p !== null) p = p.next;
if (q !== null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummy.next;
};{codeBox}

The "Add Two Numbers" problem is a great exercise for understanding linked lists and how to manipulate them to perform arithmetic operations. By breaking down the problem and tackling it step by step, we can implement a solution that efficiently adds two numbers represented as linked lists. The provided code solutions in C/C++, Java, Python, and JavaScript showcase how to approach this problem in different programming languages, catering to a wide range of developers. Happy coding!