code4java

import java.util.*;

class GFG {

	static class Node {
		int data;
		Node next;
	};

	// recursive function
	static Node addition(Node temp1, Node temp2, int size1,
						int size2)
	{
		// creating a new Node
		Node newNode = new Node();

		// base case
		if (temp1 != null && temp2 != null
			&& 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 = new Node();

		// if sizes are same then we move in both linked
		// list
		if ((temp1 != null && temp2 != null)
			&& 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 if (temp1 != null && temp2 != null) {
			// 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.
	static Node addTwoLists(Node head1, Node head2)
	{
		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 = new 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 = new 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;
	}

	static void Display(Node head)
	{
		if (head == null) {
			return;
		}
		while (head.next != null) {
			System.out.print(head.data + " -> ");
			head = head.next;
		}
		System.out.print(head.data + "\n");
	}
	// Function that adds element at the end of the Linked
	// List
	static Node push(Node head_ref, int d)
	{
		Node new_node = new Node();
		new_node.data = d;
		new_node.next = null;
		if (head_ref == null) {
			new_node.next = head_ref;
			head_ref = new_node;
			return head_ref;
		}
		Node last = head_ref;
		while (last.next != null && last != null) {
			last = last.next;
		}
		last.next = new_node;
		return head_ref;
	}
	// Driver Program for above Functions
	public static void main(String[] args)
	{
		// Creating two lists
		Node first = null;
		Node second = null;
		Node sum = null;
		first = push(first, 7);
		first = push(first, 5);
		first = push(first, 9);
		first = push(first, 4);
		first = push(first, 6);
		second = push(second, 8);
		second = push(second, 4);
		System.out.print("First List : ");
		Display(first);
		System.out.print("Second List : ");
		Display(second);
		sum = addTwoLists(first, second);
		System.out.print("Sum List : ");
		Display(sum);
	}
}

// This code contributed by shikhasingrajput