Write a Add two numbers represented by linked lists | Set 2

---

The code is for adding two numbers represented as linked lists in reverse order. Each node in the linked list represents a digit of the number, and the digits are stored in reverse order, i.e., the least significant digit is at the head of the list.

The AddTwo_LinkedList class has a nested node class, which represents a node in the linked list. Each node has a value (val) and a reference to the next node (next). The AddTwo_LinkedList class has several methods:

• printlist(node head) : This method prints the values of the nodes in the linked list, starting from the head node.
• push(int val, int list) : This method adds a new node with the given value (val) to the linked list specified by the list parameter. If list is 1, the node is added to head1 list. If list is 2, the node is added to head2 list. If list is 3, the node is added to res list.
• addsamesize(node n, node m) : This method adds the values of nodes from two linked lists of the same size (n and m) and stores the result in a new linked list (res), while considering carry from previous additions (d).
• propogatecarry(node head1) : This method propagates the carry from previous additions (d) to the remaining nodes in the longer linked list (head1) and stores the result in a new linked list (res).
• getsize(node head) : This method returns the size (number of nodes) in a linked list starting from the given head node.
• addlists(): This method adds the two linked lists head1 and head2 and stores the result in a new linked list res. It first compares the sizes of the linked lists and adds the digits of the same positions (from right to left) for the linked lists of the same size. If the sizes are not the same, it adjusts the pointers to make them the same size and then adds the digits. Finally, it handles any remaining carry and stores the result in res.
• main(String args[]): This is the entry point of the program. It creates an object of AddTwo_LinkedList class, initializes the linked lists head1 and head2 with the values from the arrays arr1 and arr2 respectively, calls the addlists() method to add the linked lists, and then calls the printlist() method to print the result.

Source Code

public class AddTwo_LinkedList
{
	class node
	{
		int val;
		node next;
 
		public node(int val)
		{
			this.val = val;
		}
	}
	void printlist(node head)
	{
		while (head != null)
		{
			System.out.print(head.val + " ");
			head = head.next;
		}
	}
 
	node head1, head2, res;
	int d;
	void push(int val, int list)
	{
		node newnode = new node(val);
		if (list == 1)
		{
			newnode.next = head1;
			head1 = newnode;
		}
		else if (list == 2)
		{
			newnode.next = head2;
			head2 = newnode;
		}
		else
		{
			newnode.next = res;
			res = newnode;
		}
 
	}
 
	void addsamesize(node n, node m)
	{
		if (n == null)
			return;
		addsamesize(n.next, m.next);
		int sum = n.val + m.val + d;
		d = sum / 10;
		sum = sum % 10;
		push(sum, 3);
 
	}
 
	node cur;
	void propogatecarry(node head1)
	{
		if (head1 != cur)
		{
			propogatecarry(head1.next);
			int sum = d + head1.val;
			d = sum / 10;
			sum %= 10;
 
			push(sum, 3);
		}
	}
 
	int getsize(node head)
	{
		int count = 0;
		while (head != null)
		{
			count++;
			head = head.next;
		}
		return count;
	}
 
	void addlists()
	{
		if (head1 == null)
		{
			res = head2;
			return;
		}
 
		if (head2 == null)
		{
			res = head1;
			return;
		}
 
		int size1 = getsize(head1);
		int size2 = getsize(head2);
		if (size1 == size2)
		{
			addsamesize(head1, head2);
		}
		else
		{
			if (size1 < size2)
			{
				node temp = head1;
				head1 = head2;
				head2 = temp;
			}
			int diff = Math.abs(size1 - size2);
			node temp = head1;
			while (diff-- >= 0)
			{
				cur = temp;
				temp = temp.next;
			}
			addsamesize(cur, head2);
			propogatecarry(head1);
		}
			if (d > 0)
				push(d, 3);
 
	}
 
	public static void main(String args[])
	{
		AddTwo_LinkedList list = new AddTwo_LinkedList();
		list.head1 = null;
		list.head2 = null;
		list.res = null;
		list.d = 0;
		int arr1[] = { 1, 2, 3, 4, 5 };
		int arr2[] = { 1, 2, 3, 4, 5 };
 
		for (int i = arr1.length - 1; i >= 0; --i)
		{			
			list.push(arr1[i], 1);
		}
 
		for (int i = arr2.length - 1; i >= 0; --i)
		{
			list.push(arr2[i], 2);
		}
		list.addlists();
		list.printlist(list.res);
	}
}

Output

2 4 6 9 0

• Previous
• Next

Example Programs

---

---

Learn All in Tamil © Designed & Developed By Tutor Joes | Privacy Policy | Terms & Conditions