10. Add two numbers represented by linked lists

10. Add two numbers represented by linked lists

Problem link :- click here

package Linked_List;

public class LinkedList__10
{
	/*
	 	Given two numbers represented by two linked list of size n1 and n2. The task 
	 	is to return a sum linked list.
	 	
	 	Method 1 :- 
	 		1 -> first reverse both the linked list.
	 		2 -> store value of any one linked list in a integer variable.
	 		3 -> just add the number(variable) to the linked list as we did in the last problem.
	 		
	 	Method 2 :-
	 		1 -> reverse both the linked list.
	 		2 -> add data of two nodes one node from list1 and other from list2.(also add c)
	 			store unit place to the new node of the sum linked list and 
	 			store the remaining (sum/10) in the carry.
	 		3 -> if any node is remaining in any one of the linked list then copy it to the 
	 			sum linked list.
	 		4 -> reverse all the linked list (list1, list2, sum)
	 		5 -> return sum.
	 */
	
	static void reverse(LinkedList list)
	{
		Node prev, cur, next;
		prev = null;
		cur = list.head;
		next = cur.next;
		
		while(cur != null)
		{
			next = cur.next;
			
			cur.next = prev;
			
			prev = cur;
			cur = next;
		}
		list.head = prev;
	}
	
	static LinkedList addTwoLinkedList(LinkedList list1, LinkedList list2)
	{
		reverse(list1);
		reverse(list2);
		
		int num1 = 0;
		int multiplier = 1;
		Node temp = list1.head;
		for(temp=list1.head; temp!=null; temp=temp.next)
		{
			num1 += (temp.data * multiplier);
			
			multiplier *= 10;
		}
		
		int num2 = 0;
		multiplier = 1;
		for(temp=list2.head; temp!=null; temp=temp.next)
		{
			num2 += (temp.data * multiplier);
			
			multiplier *= 10;
		}
		
		int sum = num1 + num2;
		LinkedList list = new LinkedList();
		
		while(sum != 0)
		{
			list.push(sum%10);
			sum = sum/10;
		}
		
		reverse(list1);
		reverse(list2);
		reverse(list);
		
		return list;
	}
	
	static LinkedList addTwoLinkedList2(LinkedList list1, LinkedList list2)
	{
		LinkedList sum = new LinkedList();
		
		reverse(list1);
		reverse(list2);
		
		Node node1 = list1.head;
		Node node2 = list2.head;
		int carry = 0;
		while(node1 != null   &&   node2 != null)
		{
			int s = node1.data + node2.data + carry;
			
			sum.push( s%10 );
			carry = s/10;
			
			node1 = node1.next;
			node2 = node2.next;
		}
		
		while(node1 != null)
		{
			int s = node1.data + carry;
			
			sum.push(s%10);
			carry = s/10;
			
			node1 = node1.next;
		}
		
		while(node2 != null)
		{
			int s = node2.data + carry;
			
			sum.push(s%10);
			carry = s/10;
			
			node2 = node2.next;
		}
		
		while(carry != 0)
		{
			sum.push(carry%10);
			carry = carry/10;
		}
		
		reverse(list1);
		reverse(list2);
		reverse(sum);
		
		return sum;
	}
	
	public static void main(String[] args)
	{
		LinkedList list1 = new LinkedList();
		list1.push(4);
		list1.push(5);
		
		LinkedList list2 = new LinkedList();
		list2.push(3);
		list2.push(4);
		list2.push(5);
		
		LinkedList sum = addTwoLinkedList2(list1, list2);
		
		printList(list1);
		printList(list2);
		System.out.println("\nSum linked list is : ");
		printList(sum);
	}

	static void printList(LinkedList list)
	{
		for(Node temp=list.head; temp!=null; temp=temp.next)
			System.out.print(temp.data + "-> ");
		System.out.println("null");
	}
}

Time complexity :- O(n1 + n2)
Space complexity :- O( max(n1, n2) )