package linkedlist.singly; //Add two numbers represented by linked lists // 245 : 5 -> 4 -> 2 // 99789 : 9 -> 8 -> 7 -> 9 -> 9 // Ans : 99341 public class Add2NumbersInLinkListType2 { static int carry=0; public static void main(String[] args) { Node templ11 = new Node(0); Node templ12 = new Node(0); Node templ13 = new Node(9); Node templ21 = new Node(0); Node templ22 = new Node(0); Node templ23 = new Node(0); Node templ24 = new Node(0); Node templ25 = new Node(9); templ11.setNext(templ12); templ12.setNext(templ13); templ21.setNext(templ22); templ22.setNext(templ23); templ23.setNext(templ24); templ24.setNext(templ25); Node res = findSum(templ11, templ21, 0); if(carry==1){ Node tempNode = new Node(carry); tempNode.setNext(res); res = tempNode; } while(res!=null){ System.out.print(res.getData() + " -> "); res=res.getNext(); } } private static Node findSum(Node l1, Node l2, int diff){ int length1 = findLength(l1); int length2 = findLength(l2); if(length1>length2){ //l1 having more nodes Node res = findSum(l1.getNext(), l2, diff--); int data = l1.getData() + carry; if(data>9){ carry=1; Node tempNode = new Node(data%10); tempNode.setNext(res); res = tempNode; }else{ carry=0; Node tempNode = new Node(data); tempNode.setNext(res); res = tempNode; } return res; }else if(length2>length1){ //l2 having more nodes Node res = findSum(l1, l2.getNext(), diff++); int data = l2.getData() + carry; if(data>9){ carry=1; Node tempNode = new Node(data%10); tempNode.setNext(res); res = tempNode; }else{ carry=0; Node tempNode = new Node(data); tempNode.setNext(res); res = tempNode; } return res; }else{ //both have same length Node res = findSumForListOfSameSize(l1, l2); return res; } } private static Node findSumForListOfSameSize(Node l1, Node l2){ if(l1==null && l2==null) return null; Node head = findSumForListOfSameSize(l1.getNext(), l2.getNext()); int temp = l1.getData() + l2.getData() + carry; if(temp>9){ carry=1; }else{ carry=0; } if(head==null){ head = new Node(temp % 10); }else{ Node tempNode = new Node(temp % 10); tempNode.setNext(head); head = tempNode; } return head; } private static int findLength(Node node){ int count=0; while(node!=null){ count++; node = node.getNext(); } return count; } }
Questions on Stack, Queues, Linkedlist, Binary Trees, Sorting, Searching, Graphs etc with solution using Java Language.
Sunday, 31 May 2015
Add two numbers represented by linked lists. (Numbers are stored in forward fashion ie least significant digit is at last node.)
Labels:
Linkedlist
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment