总结两个链接列表，其中每个节点是一个数字

Question

我正在尝试编写一个整数的函数，每个整数都由一个链表来表示，其中每个节点 - >数据都是数字0-9。最不重要的数字在列表的头部，最多的是在尾部。

这是来自Cracking the Coding Interview的书。这里是我的代码：

SinglyLinked<int>& addLists(SinglyLinked<int>& ll1, SinglyLinked<int>& ll2) 
{ 
    SinglyLinked<int> *sumList = new SinglyLinked<int>; 

    ListNode<int> *node1 = ll1.head; ListNode<int> *node2 = ll2.head; 

    int sum, carry = 0; 
    while(node1 || node2) 
    { 
    if(node1) 
     sum += node1->data; 
    if(node2) 
     sum += node2->data; 
    sum += carry; 

    carry = 0; 
    sumList->insertAtEnd(sum%10); 
    if(sum > 9) 
     carry = 1; 
    sum = 0; 
    node1 = node1->next; node2 = node2->next; 
    } 
    return *sumList; 
} 

首先，这段代码是否正确？它看起来可行，但当给定两个不同长度的链表（整数）时，它会出现故障。我想知道这个问题是否只是为了解决整数长度相同的情况。如果不是，我将如何总结两个不同长度的列表？我的天真的解决方案是存储每个列表的长度，然后使用它来创建只有一个数字将贡献的数字，直到两个整数对齐。有没有比这更优雅的东西？

Answer 1

它出现segfaults不同因为那么node1或node2指向空。

变化

节点1 = node1->下; node2 = node2-> next;

到

if (node1) 
    node1 = node1->next; 

if (node2) 
    node2 = node2->next; 

Answer 2

while(node1 || node2) 

如果任一节点可以继续下去。但预计块两个节点是有效的，当它送过来：

node1 = node1->next; node2 = node2->next; 

您在如果node1检查需要你“的nextS”：

if(node1) { 
    sum += node1->data; 
    node1 = node1->next; 
} 

等

Answer 3

有一个条件，其中节点1和节点2将指向NULL，并且如果存在来自先前位操作的进位，就不会被追加到sumlist的端部。例如，6-> 5-> 4 + 4-> 5-> 6应该是0→1→1→1，但是求和将是0→1→1。所以之前回线你应该增加：

if (carry) 
    sumList->insertAtEnd(carry); 

Answer 4

这个问题的另一个解决方案是，当你在每个列表中添加号码，把它们相加得到大总和等于两名列表之和，该款项转换成一个字符串，并将字符串的每个字符附加到一个新的列表中。希望它能帮助别人。以下是代码。

node.h文件

#ifndef node_h 
#define node_h 

class LinkedList 
{ 

private: 
    struct node 
    { 
     int data; 
     node *next; 
    }; 
    node *head; 

public: 
    LinkedList(); 
    node *createNode (int key); 
    void appendNodeBack (const int &key); 
    void printList(); 
    int SumOfNodes (const LinkedList list1); 
}; 
#endif 

node.cpp文件

#include "node.h" 
#include <math.h> 

LinkedList::LinkedList():head(NULL) {} 

LinkedList::node *LinkedList::createNode (int key) 
{ 
    node *newNode = new node; 
    newNode->data = key; 
    newNode->next = NULL; 
    return newNode; 
} 

void LinkedList::appendNodeBack (const int &key) 
{ 
    node *newNode = createNode (key); 

    //if tree is empty 
    if (head == NULL) 
    { 
     head = newNode; 
     return; 
    } 

    //if tree is not empty 
    //traverse to the last node in the list 
    node *temp = head; 
    while (temp->next != NULL) 
     temp = temp->next; 
    temp->next = newNode; 
} 

void LinkedList::printList() 
{ 
    //if tree is empty 
    if (head == NULL) 
    { 
     std::cout << "Tree is empty!\n"; 
     return; 
    } 

    //if tree not empty 
    node *temp = head; 
    while (temp != NULL) 
    { 
     std::cout << temp->data<<"-->"; 
     temp = temp->next; 

    } 
    std::cout << "NULL\n"; 
} 

int LinkedList::SumOfNodes (const LinkedList list1) 
{ 
    //find the length of the list 
    node *temp = head; 
    int count = 0; 

    while (temp != NULL) 
    { 
     count++; 
     temp = temp->next; 
    } 

    //re-assign temp to head 
    temp = head; 

    //calculate the sum 
    unsigned int sum = 0; 

    for (unsigned int i = 1; i < pow (10, count); i = i * 10) 
    { 
     sum = sum + temp->data * i; 
     temp = temp->next; 
    } 

    return sum; 
} 

的main.cpp文件

#include <iostream> 
#include "node.cpp" 

int main() 
{ 
    LinkedList list1, list2, list3; 
    list1.appendNodeBack (2); 
    list1.appendNodeBack (3); 
    list1.appendNodeBack (5); 
    list1.appendNodeBack (4); 

    list2.appendNodeBack (5); 
    list2.appendNodeBack (6); 
    list2.appendNodeBack (7); 
    list2.appendNodeBack (8); 

    list1.printList(); 
    std::cout << list1.SumOfNodes (list1) << std::endl; 

    list2.printList(); 
    std::cout << list2.SumOfNodes (list2) << std::endl; 

    unsigned int sum = list1.SumOfNodes (list1) + list2.SumOfNodes (list2); 

    //convert the number to string 
    std::string str = std::to_string (sum); 

    //append integer value to the new list 
    for (unsigned int i = 0; i < str.length(); i++) 
     list3.appendNodeBack (int (str[i] - '0')); 

    std::cout << "The new list becomes\n"; 
    list3.printList(); 

    return 0; 
}