總結兩個鏈接列表，其中每個節點是一個數字

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