1

整数を合計する関数を作成しようとしています。各整数は、各ノード->データが0〜9の数字であるリンクリストで表されます。最下位桁はリストの先頭にあり、最上位桁は末尾にあります。

これは、「コーディングインタビューのクラッキング」という本からのものです。これが私のコードです：

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

まず第一に、このコードは正しいですか？動作しているように見えますが、長さが異なる2つのリンクリスト（整数）を指定すると、セグメンテーション違反が発生します。この問題は、整数が同じ長さの場合にのみ解決することを目的としていたのではないかと思います。そうでない場合、長さの異なる2つのリストを合計するにはどうすればよいですか？私の素朴な解決策は、各リストの長さを保存し、それを使用して、2つの整数が整列するまで、数字の1つだけが寄与する数字を作成することです。それよりもエレガントなものはありますか？

4

4 に答える 4

1

node1ornode2がnullを指すため、異なる長さのリストでセグメンテーション違反が発生します。

変化する

node1 = node1-> 次; node2 = node2-> 次;

に

if (node1)
    node1 = node1->next;

if (node2)
    node2 = node2->next;
于 2012-11-01T23:44:51.530 に答える
0 
while(node1 || node2)

いずれかのノードに問題がない場合は、続行します。ただし、ブロックは、ここに到達したときに両方のノードが有効であることを期待しています。

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

if node1 チェックで「次」が必要です。

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

等

于 2012-11-01T23:42:53.247 に答える
0

node1 と node2 が NULL を指し、前の数字操作からの桁上げがある場合、サムリストの最後に追加されないという 1 つの条件があります。たとえば、6->5->4 + 4->5->6 は 0->1->1->1 のはずですが、sumlist は 0->1->1 になります。したがって、戻り行の前に次を追加する必要があります。

if (carry)
   sumList->insertAtEnd(carry);
于 2015-02-16T11:45:17.437 に答える
0

この問題の別の解決策は、各リストの数値を加算し、それらを合計して 2 つのリストの合計に等しい大きな合計を取得し、その合計を文字列に変換し、文字列の各文字を新しいリストに追加することです。それが誰かを助けることを願っています。以下はコードです。

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;
}
于 2016-02-07T19:16:44.997 に答える