Add two numbers represented by linked lists | Set 1
Given two numbers represented by two lists, write a function that returns the sum list. The sum list is a list representation of the addition of two input numbers.
Example:
Input:
List1: 5->6->3 // represents number 563
List2: 8->4->2 // represents number 842
Output:
Resultant list: 1->4->0->5 // represents number 1405
Explanation: 563 + 842 = 1405Input:
List1: 7->5->9->4->6 // represents number 75946
List2: 8->4 // represents number 84
Output:
Resultant list: 7->6->0->3->0// represents number 76030
Explanation: 75946+84=76030
Approach: Traverse both lists to the end and add preceding zeros in the list with lesser digits. Then call a recursive function on the start nodes of both lists which calls itself for the next nodes of both lists till it gets to the end. This function creates a node for the sum of the current digits and returns the carry.
The steps are:
- Traverse the two linked lists in order to add preceding zeros in case a list is having lesser digits than the other one.
- Start from the head node of both lists and call a recursive function for the next nodes.
- Continue it till the end of the lists.
- Creates a node for current digits sum and returns the carry.
Below is the implementation of this approach.
|
// C++ program to add two numbers
// represented by linked list
#include
using namespace std;
/* Linked list node */
class Node {
public:
int data;
Node* next;
};
/* Function to create a
new node with given data */
Node* newNode[int data]
{
Node* new_node = new Node[];
new_node->data = data;
new_node->next = NULL;
return new_node;
}
/* Function to insert a node at the
beginning of the Singly Linked List */
void push[Node** head_ref, int new_data]
{
/* allocate node */
Node* new_node = newNode[new_data];
/* link the old list off the new node */
new_node->next = [*head_ref];
/* move the head to point to the new node */
[*head_ref] = new_node;
}
/* Adds contents of two linked lists and
return the head node of resultant list */
Node* addTwoLists[Node* first, Node* second]
{
// res is head node of the resultant list
Node* res = NULL;
Node *temp, *prev = NULL;
int carry = 0, sum;
// while both lists exist
while [first != NULL
|| second != NULL] {
// Calculate value of next
// digit in resultant list.
// The next digit is sum of
// following things
// [i] Carry
// [ii] Next digit of first
// list [if there is a next digit]
// [ii] Next digit of second
// list [if there is a next digit]
sum = carry + [first ? first->data : 0]
+ [second ? second->data : 0];
// update carry for next calculation
carry = [sum >= 10] ? 1 : 0;
// update sum if it is greater than 10
sum = sum % 10;
// Create a new node with sum as data
temp = newNode[sum];
// if this is the first node then
// set it as head of the resultant list
if [res == NULL]
res = temp;
// If this is not the first
// node then connect it to the rest.
else
prev->next = temp;
// Set prev for next insertion
prev = temp;
// Move first and second
// pointers to next nodes
if [first]
first = first->next;
if [second]
second = second->next;
}
if [carry > 0]
temp->next = newNode[carry];
// return head of the resultant list
return res;
}
Node* reverse[Node* head]
{
if [head == NULL || head->next == NULL]
return head;
/* reverse the rest list and put
the first element at the end */
Node* rest = reverse[head->next];
head->next->next = head;
head->next = NULL;
/* fix the head pointer */
return rest;
}
// A utility function to print a linked list
void printList[Node* node]
{
while [node != NULL] {
cout data next;
}
cout 5->9->4->6
push[&first, 6];
push[&first, 4];
push[&first, 9];
push[&first, 5];
push[&first, 7];
printf["First List is "];
printList[first];
// create second list 8->4
push[&second, 4];
push[&second, 8];
cout next = NULL;
return new_node;
}
/* Function to insert a node
at the beginning of the Singly Linked List */
void push[struct Node** head_ref, int new_data]
{
/* allocate node */
struct Node* new_node = newNode[new_data];
/* link the old list off the new node */
new_node->next = [*head_ref];
/* move the head to point to the new node */
[*head_ref] = new_node;
}
/* Adds contents of two linked
lists and return the head node
of resultant list */
struct Node* addTwoLists[struct Node* first,
struct Node* second]
{
// res is head node of the resultant list
struct Node* res = NULL;
struct Node *temp, *prev = NULL;
int carry = 0, sum;
// while both lists exist
while [first != NULL || second != NULL] {
// Calculate value of next
// digit in resultant list.
// The next digit is sum
// of following things
// [i] Carry
// [ii] Next digit of first
// list [if there is a next digit]
// [ii] Next digit of second
// list [if there is a next digit]
sum = carry + [first ? first->data : 0]
+ [second ? second->data : 0];
// Update carry for next calculation
carry = [sum >= 10] ? 1 : 0;
// Update sum if it is greater than 10
sum = sum % 10;
// Create a new node with sum as data
temp = newNode[sum];
// if this is the first node then
// set it as head of the resultant list
if [res == NULL]
res = temp;
// If this is not the first node
// then connect it to the rest.
else
prev->next = temp;
// Set prev for next insertion
prev = temp;
// Move first and second
// pointers to next nodes
if [first]
first = first->next;
if [second]
second = second->next;
}
if [carry > 0]
temp->next = newNode[carry];
// return head of the resultant list
return res;
}
// A utility function to print a linked list
void printList[struct Node* node]
{
while [node != NULL] {
printf["%d ", node->data];
node = node->next;
}
printf["\n"];
}
/* Driver code */
int main[void]
{
struct Node* res = NULL;
struct Node* first = NULL;
struct Node* second = NULL;
// create first list 7->5->9->4->6
push[&first, 6];
push[&first, 4];
push[&first, 9];
push[&first, 5];
push[&first, 7];
printf["First List is "];
printList[first];
// create second list 8->4
push[&second, 4];
push[&second, 8];
printf["Second List is "];
printList[second];
// Add the two lists and see result
res = addTwoLists[first, second];
printf["Resultant list is "];
printList[res];
return 0;
}
|
|
// Java program to add two numbers
// represented by linked list
class LinkedList {
static Node head1, head2;
static class Node {
int data;
Node next;
Node[int d] {
data = d;
next = null;
}
}
/* Adds contents of two linked lists and prints it */
void addTwoLists[Node first, Node second] {
Node start1 = new Node[0];
start1.next = first;
Node start2 = new Node[0];
start2.next = second;
addPrecedingZeros[start1, start2];
Node result = new Node[0];
if [sumTwoNodes[start1.next, start2.next, result] == 1] {
Node node = new Node[1];
node.next = result.next;
result.next = node;
}
printList[result.next];
}
/* Adds lists and returns the carry */
private int sumTwoNodes[Node first, Node second, Node result] {
if [first == null] {
return 0;
}
int number = first.data + second.data + sumTwoNodes[first.next, second.next, result];
Node node = new Node[number % 10];
node.next = result.next;
result.next = node;
return number / 10;
}
/* Appends preceding zeros in case a list is having lesser nodes than the other one*/
private void addPrecedingZeros[Node start1, Node start2] {
Node next1 = start1.next;
Node next2 = start2.next;
while [next1 != null && next2 != null] {
next1 = next1.next;
next2 = next2.next;
}
if [next1 == null && next2 != null] {
while [next2 != null] {
Node node = new Node[0];
node.next = start1.next;
start1.next = node;
next2 = next2.next;
}
} else if [next2 == null && next1 != null] {
while [next1 != null] {
Node node = new Node[0];
node.next = start2.next;
start2.next = node;
next1 = next1.next;
}
}
}
/* Utility function to print a linked list */
void printList[Node head] {
while [head != null] {
System.out.print[head.data + " "];
head = head.next;
}
System.out.println[""];
}
// Driver Code
public static void main[String[] args] {
LinkedList list = new LinkedList[];
// creating first list
list.head1 = new Node[7];
list.head1.next = new Node[5];
list.head1.next.next = new Node[9];
list.head1.next.next.next = new Node[4];
list.head1.next.next.next.next = new Node[6];
System.out.print["First List is "];
list.printList[head1];
// creating second list
list.head2 = new Node[8];
list.head2.next = new Node[4];
System.out.print["Second List is "];
list.printList[head2];
System.out.print["Resultant List is "];
// add the two lists and see the result
list.addTwoLists[head1, head2];
}
// this code is contributed by *Saurabh321Gupta*
}
|
|
# Python program to add two numbers represented by linked list
# Node class
class Node:
# Constructor to initialize the node object
def __init__[self, data]:
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__[self]:
self.head = None
# Function to insert a new node at the beginning
def push[self, new_data]:
new_node = Node[new_data]
new_node.next = self.head
self.head = new_node
# Add contents of two linked lists and return the head
# node of resultant list
def addTwoLists[self, first, second]:
prev = None
temp = None
carry = 0
# While both list exists
while[first is not None or second is not None]:
# Calculate the value of next digit in
# resultant list
# The next digit is sum of following things
# [i] Carry
# [ii] Next digit of first list [if ther is a
# next digit]
# [iii] Next digit of second list [ if there
# is a next digit]
fdata = 0 if first is None else first.data
sdata = 0 if second is None else second.data
Sum = carry + fdata + sdata
# update carry for next calculation
carry = 1 if Sum >= 10 else 0
# update sum if it is greater than 10
Sum = Sum if Sum < 10 else Sum % 10
# Create a new node with sum as data
temp = Node[Sum]
# if this is the first node then set it as head
# of resultant list
if self.head is None:
self.head = temp
else:
prev.next = temp
# Set prev for next insertion
prev = temp
# Move first and second pointers to next nodes
if first is not None:
first = first.next
if second is not None:
second = second.next
if carry > 0:
temp.next = Node[carry]
# Utility function to print the linked LinkedList
def printList[self]:
temp = self.head
while[temp]:
print [temp.data,end=' ']
temp = temp.next
# Driver code
first = LinkedList[]
second = LinkedList[]
# Create first list
first.push[6]
first.push[4]
first.push[9]
first.push[5]
first.push[7]
print ["First List is ",end=' ']
first.printList[]
# Create second list
second.push[4]
second.push[8]
print ["\nSecond List is",end=' ']
second.printList[]
# Add the two lists and see result
res = LinkedList[]
res.addTwoLists[first.head, second.head]
print ["\nResultant list is",end=' ']
res.printList[]
# This code is contributed by Nikhil Kumar Singh[nickzuck_007]
|
|
// C# program to add two numbers
// represented by linked list
using System;
public class LinkedList {
Node head1, head2;
public class Node {
public int data;
public Node next;
public Node[int d]
{
data = d;
next = null;
}
}
/* Adds contents of two linked lists
and return the head node of resultant list */
Node addTwoLists[Node first, Node second]
{
// res is head node of the resultant list
Node res = null;
Node prev = null;
Node temp = null;
int carry = 0, sum;
// while both lists exist
while [first != null || second != null] {
// Calculate value of next digit in resultant
// list. The next digit is sum of following
// things [i] Carry [ii] Next digit of first
// list [if there is a next digit] [ii] Next
// digit of second list [if there is a next
// digit]
sum = carry + [first != null ? first.data : 0]
+ [second != null ? second.data : 0];
// update carry for next calculation
carry = [sum >= 10] ? 1 : 0;
// update sum if it is greater than 10
sum = sum % 10;
// Create a new node with sum as data
temp = new Node[sum];
// if this is the first node then set it as head
// of the resultant list
if [res == null] {
res = temp;
}
// If this is not the first
// node then connect it to the rest.
else {
prev.next = temp;
}
// Set prev for next insertion
prev = temp;
// Move first and second pointers to next nodes
if [first != null] {
first = first.next;
}
if [second != null] {
second = second.next;
}
}
if [carry > 0] {
temp.next = new Node[carry];
}
// return head of the resultant list
return res;
}
/* Utility function to print a linked list */
void printList[Node head]
{
while [head != null] {
Console.Write[head.data + " "];
head = head.next;
}
Console.WriteLine[""];
}
// Driver code
public static void Main[String[] args]
{
LinkedList list = new LinkedList[];
// creating first list
list.head1 = new Node[7];
list.head1.next = new Node[5];
list.head1.next.next = new Node[9];
list.head1.next.next.next = new Node[4];
list.head1.next.next.next.next = new Node[6];
Console.Write["First List is "];
list.printList[list.head1];
// creating second list
list.head2 = new Node[8];
list.head2.next = new Node[4];
Console.Write["Second List is "];
list.printList[list.head2];
// add the two lists and see the result
Node rs = list.addTwoLists[list.head1, list.head2];
Console.Write["Resultant List is "];
list.printList[rs];
}
}
// This code contributed by Rajput-Ji
|
|
// Javascript program to add two numbers
// represented by linked list
var head1, head2;
class Node {
constructor[val] {
this.data = val;
this.next = null;
}
}
/*
Adds contents of two linked lists and return
the head node of resultant list
*/
function addTwoLists[ first, second] {
// res is head node of the resultant list
var res = null;
var prev = null;
var temp = null;
var carry = 0, sum;
// while both lists exist
while [first != null || second != null] {
// Calculate value of next
// digit in resultant list.
// The next digit is sum
// of following things
// [i] Carry
// [ii] Next digit of first
// list [if there is a next digit]
// [ii] Next digit of second
// list [if there is a next digit]
sum = carry + [first != null ? first.data : 0] +
[second != null ? second.data : 0];
// update carry for next calculation
carry = [sum >= 10] ? 1 : 0;
// update sum if it is greater than 10
sum = sum % 10;
// Create a new node with sum as data
temp = new Node[sum];
// if this is the first node then set
// it as head of the resultant list
if [res == null] {
res = temp;
}
// If this is not the first
// node then connect it to the rest.
else {
prev.next = temp;
}
// Set prev for next insertion
prev = temp;
// Move first and second pointers
// to next nodes
if [first != null] {
first = first.next;
}
if [second != null] {
second = second.next;
}
}
if [carry > 0] {
temp.next = new Node[carry];
}
// return head of the resultant list
return res;
}
/* Utility function to print a linked list */
function printList[ head] {
while [head != null] {
document.write[head.data + " "];
head = head.next;
}
document.write["
"];
}
// Driver Code
// creating first list
head1 = new Node[7];
head1.next = new Node[5];
head1.next.next = new Node[9];
head1.next.next.next = new Node[4];
head1.next.next.next.next = new Node[6];
document.write["First List is "];
printList[head1];
// creating second list
head2 = new Node[8];
head2.next = new Node[4];
document.write["Second List is "];
printList[head2];
// add the two lists and see the result
rs = addTwoLists[head1, head2];
document.write["Resultant List is "];
printList[rs];
// This code contributed by aashish2995
|
Complexity Analysis:
-
Time Complexity: O[m + n], where m and n are numbers of nodes in first and second lists respectively.
The lists need to be traversed only once. -
Space Complexity: O[m + n].
A temporary linked list is needed to store the output number
Method 2[Using STL]: Using the stack data structure
Approach :
- Create 3 stacks namely s1,s2,s3.
- Fill s1 with Nodes of list1 and fill s2 with nodes of list2.
- Fill s3 by creating new nodes and setting the data of new nodes to the sum of s1.top[], s2.top[] and carry until list1 and list2 are empty .
- If the sum >9
- set carry 1
- else
- set carry 0
- Create a Node[say prev] that will contain the head of the sum List.
- Link all the elements of s3 from top to bottom
- return prev
Code:
|
// C++ program to add two numbers represented by Linked
// Lists using Stack
#include
using namespace std;
class Node {
public:
int data;
Node* next;
};
Node* newnode[int data]
{
Node* x = new Node[];
x->data = data;
return x;
}
// function that returns the sum of two numbers represented
// by linked lists
Node* addTwoNumbers[Node* l1, Node* l2]
{
Node* prev = NULL;
// Create 3 stacks
stack s1, s2, s3;
// Fill first stack with first List Elements
while [l1 != NULL] {
s1.push[l1];
l1 = l1->next;
}
// Fill second stack with second List Elements
while [l2 != NULL] {
s2.push[l2];
l2 = l2->next;
}
int carry = 0;
// Fill the third stack with the sum of first and second
// stack
while [!s1.empty[] && !s2.empty[]] {
int sum = s1.top[]->data + s2.top[]->data + carry;
Node* temp = newnode[sum % 10];
s3.push[temp];
if [sum > 9] {
carry = 1;
}
else {
carry = 0;
}
s1.pop[];
s2.pop[];
}
while [!s1.empty[]] {
int sum = carry + s1.top[]->data;
Node* temp = newnode[sum % 10];
s3.push[temp];
if [sum > 9] {
carry = 1;
}
else {
carry = 0;
}
s1.pop[];
}
while [!s2.empty[]] {
int sum = carry + s2.top[]->data;
Node* temp = newnode[sum % 10];
s3.push[temp];
if [sum > 9] {
carry = 1;
}
else {
carry = 0;
}
s2.pop[];
}
// If carry is still present create a new node with
// value 1 and push it to the third stack
if [carry == 1] {
Node* temp = newnode[1];
s3.push[temp];
}
// Link all the elements inside third stack with each
// other
if [!s3.empty[]]
prev = s3.top[];
while [!s3.empty[]] {
Node* temp = s3.top[];
s3.pop[];
if [s3.size[] == 0] {
temp->next = NULL;
}
else {
temp->next = s3.top[];
}
}
return prev;
}
// utility functions
// Function that displays the List
void Display[Node* head]
{
if [head == NULL] {
return;
}
while [head->next != NULL] {
cout data next;
}
cout data next = NULL;
if [*head_ref == NULL] {
new_node->next = *head_ref;
*head_ref = new_node;
return;
}
Node* last = *head_ref;
while [last->next != NULL && last != NULL] {
last = last->next;
}
last->next = new_node;
return;
}
// Driver Program for above Functions
int main[]
{
// Creating two lists
// first list = 9 -> 5 -> 0
// second List = 6 -> 7
Node* first = NULL;
Node* second = NULL;
Node* sum = NULL;
push[&first, 9];
push[&first, 5];
push[&first, 0];
push[&second, 6];
push[&second, 7];
cout 7
Sum List : 1 -> 0 -> 1 -> 7
Another Approach with time complexity O[N]: The given approach works as following steps:
C++
|