Add two numbers in Linked List
NinjacartThe problem
Given two non-empty linked lists **linkedList1 **and **linkedList2 **which represent two non-negative integers.
The digits are stored in **reverse **order with each node storing one digit. Add two numbers and return the sum as a linked list.
-
The sum Linked List will be in reverse order as well.
-
The Two given Linked Lists represent numbers without any leading zeros, except when the number is zero itself.
Input: linkedList1 = [5, 4], linkedList2 = [4] Output: [9, 4] Explanation: linkedList1 = 45, linkedList2 = 4. linkedList1 + linkedList2 = 45 + 4 = 49. The sum is 49 and when prepare the linked list we reverse the number [9, 4]
Input: linkedList1 = [4, 5, 6], linkedList2 = [1, 2, 3] Output: [5, 7, 9] Explanation: linkedList1 = 654, linkedList2 = 321. linkedList1 + linkedList2 = 654 + 321 = 975. The sum is 975 and when prepare the linked list we reverse the number [5, 7, 9]The sum
Input: linkedList1 = [1], linkedList2 = [8, 7]
- 1 <= Number of nodes in each Linked List <= 100
- 0 <= value of each node in both Linked List <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
cpp
/*
Definition of singly linked list:
class ListNode{
public:
int data;
ListNode *next;
ListNode() : data(0), next(nullptr) {}
ListNode(int x) : data(x), next(nullptr) {}
ListNode(int x, ListNode *next) : data(x), next(next) {}
};
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* &linkedList1, ListNode* &linkedList2) {
//your code goes here
}
};java
/*
Definition of singly linked list:
class ListNode{
public int data;
public ListNode next;
ListNode() { data = 0; next = null; }
ListNode(int x) { data = x; next = null; }
ListNode(int x, ListNode next) { data = x; this.next = next; }
}
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//YOUR CODE GOES HERE
}
}python
# Definition of singly linked list:
# class ListNode:
# def __init__(self, x=0, next=None):
# self.data = x
# self.next = next
class Solution:
def addTwoNumbers(self, linkedList1, linkedList2):
"""
:type linkedList1: Optional[ListNode]
:type linkedList2: Optional[ListNode]
:rtype: Optional[ListNode]
"""javascript
/*
Definition of singly linked list:
class ListNode{
constructor(x, next){
this.data = x;
this.next = next;
}
}
*/
/**
* @param {ListNode} linkedList1
* @param {ListNode} linkedList2
* @return {ListNode}
*/
class Solution {
addTwoNumbers(linkedList1, linkedList2) {
//your code goes here
}
}csharp
/*
Definition of singly linked list:
class ListNode{
public int data;
public ListNode next;
public ListNode() { data = 0; next = null; }
public ListNode(int x) { data = x; next = null; }
public ListNode(int x, ListNode next) { data = x; this.next = next; }
}
*/
public class Solution {
public ListNode AddTwoNumbers(ListNode linkedList1, ListNode linkedList2) {
//YOUR CODE GOES HERE
}
}go
/*
Definition of singly linked list:
type ListNode struct {
data int
next *ListNode
}
*/
func addTwoNumbers(linkedList1 *ListNode, linkedList2 *ListNode) *ListNode {
//your code goes here
}Stuck? Show a way to structure it+
- 01Clarify digit order
- 02Iterate while either pointer or carry exists
- 03Compute digit and next carry, appending to a dummy tail
- 04Return dummy.next, reversing if the representation requires it
Reference answer
Then expect these follow-ups
How do you solve forward-order lists without reversal?
Tests: follow-up reasoning
How do you handle arbitrary bases?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question