添加到边缘案例表示的数字

Question

我正在阅读算法，将两个数字相加，这些数字由Gayle Laakmann在第108页的Crack The Coding Interview一书中的链表表示。如果你没有这本书，问题，算法和代码如下：

问题

您有两个由链表表示的数字，其中每个节点包含一个数字。数字以相反的顺序存储，例如1 的数字位于列表的顶部。编写一个函数将这两个数字相加，并将 UM 作为链表返回。

例

输入：(3->1->5),(5->9->2)

输出：8->0->8

算法

1. 结果数据 = (节点 1 + 节点 2 + 早期进位( % 10
2. 如果节点 1 + 节点 2> 10，则在下一个加法中携带 1
3. 添加两个节点的尾部，沿进位传递

法典

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;
}

看到if (l1 == null && l2 == null)后想到的明显事情是，如果两个数字都是空并且仍然有一个进位怎么办 - 就像我们添加 999 + 999 一样。这不会导致错误的答案吗？如果这导致正确答案，我看不出如何。如果这导致错误的答案，我们如何得到正确的答案？将前几行更改为

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

做这个把戏？

Answer 1

条件应为：

value > 9 ? 1 : 0 

在以下递归调用中：

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

Answer 2

这是我有效的解决方案：

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

我使用 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;
}

}

二等舱：

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;
}

基本上，最后一个 if 条件检查添加是否结束并且还剩下进位。如果是这种情况，那么它将被添加到自己的节点并附加到答案中。

Answer 5

我使用 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)