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
Hiring now
Software engineer roles are open right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY
Next question