Add to numbers represented by linked list - Edge

Question

I read the algorithm to add two numbers represented by a linked list from Crack The Coding Interview by Gayle Laakmann on page 108. If you do not have the book, the question, algorithm and code look like this:

Question

You have two numbers represented by a linked list, where each node contains one digit. The numbers are stored in reverse order, such that the first digit is at the head of the list. Write a function that adds two numbers and returns um as a linked list.

Example

Input: (3->1->5),(5->9->2)

Output: 8->0->8

Algorithm

• result.data = (node1 + node2 + previously migrate)% 10
• if node1 + node2> 10 then transfer 1 to the next addition
• add tails of two nodes running along the carry

Code

 LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2, int carry) { if (l1 == null && l2 == null) { return null; } LinkedListNode result = new LinkedListNode(carry, null, null); int value = carry; if (l1 != null) { value += l1.data; } if (l2 != null) { value += l2.data; } result.data = value % 10; LinkedListNode more = addLists(l1 == null ? null : l1.next, l2 == null ? null : l2.next, value > 10 ? 1 : 0); result.setNext(more); return result; } 

The obvious thing that comes to mind after looking at if (l1 == null && l2 == null) is that if both digits are zero and adding 999 + 999 still carries over. Will this lead to a wrong answer? If this leads to the correct answer, I do not understand how to do it. If this leads to a wrong answer, how can we get the right answer? Would change the first few lines to

 LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2, int carry = null) { if (l1 == null && l2 == null) { return carry; } 

do the trick?

Answer 1

The condition must be:

 value > 9 ? 1 : 0 

in the following recursive call:

 LinkedListNode more = addLists(l1 == null ? null : l1.next, l2 == null ? null : l2.next, value > 10 ? 1 : 0); 

Answer 2

Here is my solution that works:

 public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return addTwoNumbers(l1, l2, 0); } public ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry) { int value; if(carry > 0) { // handle negative values for carry value = carry; } else { value = 0; } if(l1 == null && l2 == null){ if(value > 0) { // here we have only carry to bother. // if it is zero, no need to create node return new ListNode(value); } else { return null; } } if(l1 != null){ value += l1.val; } if(l2 != null){ value += l2.val; } carry = value/10; ListNode n1 = new ListNode(value%10); n1.next = addTwoNumbers(l1 != null ? l1.next : null, l2 != null ? l2.next : null, carry); return n1; } 

}

Answer 3

My solution with DList!

 public class DListNode { public int item; public DListNode prev; public DListNode next; DListNode() { item = 0; prev = null; next = null; } public DListNode(int i){ item = i; prev = null; next = null; } 

}

Second class:

 public class DList { protected DListNode head; protected DListNode tail;`` protected long size; public DList() { head = null; tail = null; size = 0; } public DList(int a) { head = new DListNode(); tail = head; head.item = a; size = 1; } public DList(int a, int b) { head = new DListNode(); head.item = a; tail = new DListNode(); tail.item = b; head.next = tail; tail.prev = head; size = 2; } public void insertFront(int i) { if (size == 0) { head = new DListNode(i); tail = head; } else { DListNode temp = new DListNode(i); head.prev = temp; temp.next = head; head = temp; } size++; } public String toString() { String result = "[ "; DListNode current = head; while (current != null) { result = result + current.item + " "; current = current.next; } return result + "]"; } public long getSize() { return size; } public DListNode getHead() { return head; } public DListNode getTail() { return tail; } public DList addList(DList lst1, DList lst2) { DList result = new DList(); DListNode tail1 = lst1.getTail(); DListNode tail2 = lst2.getTail(); int carry = 0; if (lst1 == null || lst2 == null) { return null; } if (lst1.getSize() != lst2.getSize()) { if (lst1.getSize() < lst2.getSize()) { long diff = lst2.getSize() - lst1.getSize(); long a = 0; while (a < diff) { lst1.insertFront(0); a++; } } else { long diff = lst1.getSize() - lst2.getSize(); long a = 0; while (a < diff) { lst2.insertFront(0); a++; } } } int a = 0; int resultValue; while (a <= lst1.getSize()) { if (tail1 != null && tail2 != null) { int l1 = tail1.item; int l2 = tail2.item; int sum = carry + l1 + l2; if (a == lst1.getSize() - 1) { resultValue = sum % 10; carry = 1; result.insertFront(carry); result.insertFront(resultValue); } else if (sum >= 10) { resultValue = sum % 10; carry = 1; result.insertFront(resultValue); } else { resultValue = sum; carry = 0; result.insertFront(resultValue); } //result.insertFront(resultValue); tail1 = tail1.prev; tail2 = tail2.prev; } a++; } System.out.println("List1 is: " + lst1.toString()); System.out.println("List2 is: " + lst2.toString()); return result; } public static void main(String[] args) { DList d1 = new DList(); DList d2 = new DList(); d1.insertFront(1); d1.insertFront(5); d1.insertFront(3); d2.insertFront(4); d2.insertFront(5); d2.insertFront(7); DList d3 = new DList(); System.out.println(d3.addList(d1, d2)); } 

}

Answer 4

 Node* addReversed(Node *l1, Node *l2, int carry) { if (l1 == NULL && l2 == NULL && carry == 0) return NULL; int value = carry; if (l1 != NULL) value += l1->data; if (l2 != NULL) value += l2->data; Node *answer = new Node(value%10); if (l1 != NULL || l2 != NULL) { Node *temp = addReversed(l1 != NULL ? l1->next : NULL, l2 != NULL ? l2->next : NULL, value >= 10 ? 1 : 0); answer->next = temp; } else { if (value >= 10) { Node *temp = new Node(1); answer->next = temp; } } return answer; } 

Basically, the last if condition checks if the addition has finished and there is still a carryover. If so, it is added to the node and added to the answer.

Answer 5

My solution using Python3

 class Node: def __init__(self, value): self.value = value self.next = None class LinkedList: def __init__(self): self.head = None self.tail = None def addNode(self, inse): nde = Node(inse) if self.head == None: self.head = nde self.tail = nde else: self.tail.next = nde self.tail = nde def __str__(self): nodestore = [str(self.head.value)] index = self.head while index.next != None: index = index.next nodestore.append(str(index.value)) return "->".join(nodestore) def addTwo(self, fi, se): self.head = None self.tail = None carry = 0 while (fi is not None or se is not None): fdata = 0 if fi is None else fi.value sdata = 0 if se is None else se.value Sum = carry + fdata + sdata carry = 1 if Sum >= 10 else 0 Sum = Sum if Sum < 10 else Sum % 10 temp = Node(Sum) if self.head == None: self.head = temp else: self.tail.next = temp self.tail = temp if fi is not None: fi = fi.next if se is not None: se = se.next if carry > 0: #for first digit = 1 self.tail.next = Node(carry) def randomLinkedList(leng, min, max): from random import randint rll = LinkedList() for i in range(leng): value = randint(min, max) rll.addNode(value) return rll l1 = randomLinkedList(3,0,9) l2 = randomLinkedList(3,0,9) print (l1) print (l2) res = LinkedList() res.addTwo(l1.head, l2.head) print (res)