Add two numbers represented by linked lists

version.cpp

// 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) 
{ 
	Node* res = NULL; // res is head node of the resultant list 
	Node *temp, *prev = NULL; 
	int carry = 0, sum; 

	while (first != NULL || second != NULL) //while both lists exist 
	{ 
		// 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 calulation 
		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(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); 

	// Add the two lists and see result 
	res = addTwoLists(first, second); 
	cout<<"Resultant list is "; 
	printList(res); 

return 0; 
} 

// This code is contributed by rathbhupendra 

version.py

# 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, 
			temp = temp.next

# Driver program to test above function 
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 ", 
first.printList() 

# Create second list 
second.push(4) 
second.push(8) 
print "\nSecond List is ", 
second.printList() 

# Add the two lists and see result 
res = LinkedList() 
res.addTwoLists(first.head, second.head) 
print "\nResultant list is ", 
res.printList() 

Traverse both lists and One by one pick nodes of both lists and add the values. If the sum is more than 10 then make carry as 1 and reduce sum. If one list has more elements than the other then consider remaining values of this list as 0.