4

我正在阅读算法，以添加由 Gayle Laakmann 在第 108 页的《 Crack The Coding Interview》一书中的链表表示的两个数字。如果您没有这本书，那么问题、算法和代码如下：

问题

您有两个由链表表示的数字，其中每个节点包含一个数字。数字以相反的顺序存储，因此 1 的数字位于列表的头部。编写一个函数，将两个数字相加并以链表的形式返回 um。

例子

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

输出：8->0->8

算法

  1. result.data = (node1 + node2 +earlier carry) % 10
  2. 如果 node1 + node2 > 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;   
}

做这个把戏？

4

5 回答 5

4

条件应该是：

value > 9 ? 1 : 0

在以下递归调用中：

LinkedListNode more = addLists(l1 == null ? null : l1.next, l2 == null ? null : l2.next, value > 10 ? 1 : 0);
 // space
于 2013-06-21T04:02:48.540 回答
1

这是我的有效解决方案：

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

}

于 2015-01-14T18:03:58.573 回答
1

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

}

}

于 2016-11-20T04:17:53.133 回答
0 
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 条件检查加法是否结束并且是否还有进位。如果是这种情况，则将其添加到自己的节点并附加到答案中。

于 2015-08-22T09:59:07.597 回答
0

我使用 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)
于 2016-10-02T23:21:45.117 回答