Add two numbers represented by linked lists leetcode

// C++ program to add two numbers

// represented by linked list

#include <bits/stdc++.h>

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 << node->data << " ";

node = node->next;

}

cout << endl;

}

/* Driver code */

int main(void)

{

Node* res = NULL;

Node* first = NULL;

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);

cout << "Second List is ";

printList(second);

// reverse both the lists

first = reverse(first);

second = reverse(second);

// Add the two lists

res = addTwoLists(first, second);

// reverse the res to get the sum

res = reverse(res);

cout << "Resultant list is ";

printList(res);

return 0;

}

#include <stdio.h>

#include <stdlib.h>

/* Linked list node */

struct Node {

int data;

struct Node* next;

};

/* Function to create a new node with given data */

struct Node* newNode(int data)

{

struct Node* new_node

= (struct Node*)malloc(sizeof(struct 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(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 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

<script>

// 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("<br/>");

}

// 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

</script>

// C++ program to add two numbers represented by Linked

// Lists using Stack

#include <bits/stdc++.h>

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<Node*> 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 << head->data << " -> ";

head = head->next;

}

cout << head->data << endl;

}

// Function that adds element at the end of the Linked List

void push(Node** head_ref, int d)

{

Node* new_node = newnode(d);

new_node->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 << "First List : ";

Display(first);

cout << "Second List : ";

Display(second);

sum = addTwoNumbers(first, second);

cout << "Sum List : ";

Display(sum);

return 0;

}

#include <iostream>

using namespace std;

struct Node {

int data;

struct Node* next;

};

// recursive function

Node* addition(Node* temp1, Node* temp2, int size1,

int size2)

{

// creating a new Node

Node* newNode

= (struct Node*)malloc(sizeof(struct Node));

// base case

if (temp1->next == NULL && temp2->next == NULL) {

// addition of current nodes which is the last nodes

// of both linked lists

newNode->data = (temp1->data + temp2->data);

// set this current node's link null

newNode->next = NULL;

// return the current node

return newNode;

}

// creating a node that contains sum of previously added

// number

Node* returnedNode

= (struct Node*)malloc(sizeof(struct Node));

// if sizes are same then we move in both linked list

if (size2 == size1) {

// recursively call the function

// move ahead in both linked list

returnedNode = addition(temp1->next, temp2->next,

size1 - 1, size2 - 1);

// add the current nodes and append the carry

newNode->data = (temp1->data + temp2->data)

+ ((returnedNode->data) / 10);

}

// or else we just move in big linked list

else {

// recursively call the function

// move ahead in big linked list

returnedNode = addition(temp1, temp2->next, size1,

size2 - 1);

// add the current node and carry

newNode->data

= (temp2->data) + ((returnedNode->data) / 10);

}

// this node contains previously added numbers

// so we need to set only rightmost digit of it

returnedNode->data = (returnedNode->data) % 10;

// set the returned node to the current node

newNode->next = returnedNode;

// return the current node

return newNode;

}

// Function to add two numbers represented by nexted list.

struct Node* addTwoLists(struct Node* head1,

struct Node* head2)

{

struct Node *temp1, *temp2, *ans = NULL;

temp1 = head1;

temp2 = head2;

int size1 = 0, size2 = 0;

// calculating the size of first linked list

while (temp1 != NULL) {

temp1 = temp1->next;

size1++;

}

// calculating the size of second linked list

while (temp2 != NULL) {

temp2 = temp2->next;

size2++;

}

Node* returnedNode

= (struct Node*)malloc(sizeof(struct Node));

// traverse the bigger linked list

if (size2 > size1) {

returnedNode = addition(head1, head2, size1, size2);

}

else {

returnedNode = addition(head2, head1, size2, size1);

}

// creating new node if head node is >10

if (returnedNode->data >= 10) {

ans = (struct Node*)malloc(sizeof(struct Node));

ans->data = (returnedNode->data) / 10;

returnedNode->data = returnedNode->data % 10;

ans->next = returnedNode;

}

else

ans = returnedNode;

// return the head node of linked list that contains

// answer

return ans;

}

void Display(Node* head)

{

if (head == NULL) {

return;

}

while (head->next != NULL) {

cout << head->data << " -> ";

head = head->next;

}

cout << head->data << endl;

}

// Function that adds element at the end of the Linked List

void push(Node** head_ref, int d)

{

Node* new_node

= (struct Node*)malloc(sizeof(struct Node));

new_node->data = d;

new_node->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

Node* first = NULL;

Node* second = NULL;

Node* sum = NULL;

push(&first, 5);

push(&first, 6);

push(&first, 3);

push(&second, 8);

push(&second, 4);

push(&second, 2);

cout << "First List : ";

Display(first);

cout << "Second List : ";

Display(second);

sum = addTwoLists(first, second);

cout << "Sum List : ";

Display(sum);

return 0;

}

// This code is contributed by Dharmik Parmar