List Add 1

18 Jun 2019

// Recursive Java program to add 1 to a linked list 
int addWithCarry(Node head) 
{ 

	// If linked list is empty, then 
	// return carry 
	if (head == null) 
		return 1; 

	// Add carry returned be next node call 
	int res = head.data + addWithCarry(head.next); 

	// Update data and return new carry 
	head.data = (res) % 10; 
	return (res) / 10; 
} 

// This function mainly uses addWithCarry(). 
Node addOne(Node head) 
{ 

	// Add 1 to linked list from end to beginning 
	int carry = addWithCarry(head); 

	// If there is carry after processing all nodes, 
	// then we need to add a new node to linked list 
	if (carry > 0) 
	{ 
		Node newNode = newNode(carry); 
		newNode.next = head; 
		return newNode; // New node becomes head now 
	} 

	return head; 
} 


//reverse -> add 1 -> reverse
/* 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 reverse the linked list */
Node reverse(Node head) 
{ 
	Node prev = null; 
	Node current = head; 
	Node next = null; 
	while (current != null) 
	{ 
		next = current.next; 
		current.next = prev; 
		prev = current; 
		current = next; 
	} 
	return prev; 
} 

/* Adds one to a linked lists and return the head 
node of resultant list */
Node addOneUtil(Node head) 
{ 
	// res is head node of the resultant list 
	Node res = head; 
	Node temp = null, prev = null; 

	int carry = 1, sum; 

	while (head != 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 head list (if there is a 
		// next digit) 
		sum = carry + head.data; 

		// 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 
		head.data = sum; 

		// Move head and second pointers to next nodes 
		temp = head; 
		head = head.next; 
	} 

	// if some carry is still there, add a new node to 
	// result list. 
	if (carry > 0) 
		temp.next = newNode(carry); 

	// return head of the resultant list 
	return res; 
} 

// This function mainly uses addOneUtil(). 
Node addOne(Node head) 
{ 
	// Reverse linked list 
	head = reverse(head); 

	// Add one from left to right of reversed 
	// list 
	head = addOneUtil(head); 

	// Reverse the modified list 
	return reverse(head); 
}