sum of two linked lists always starts with 0

Question

I want to create two linked lists by taking user input, and then add them and store the sum in a third linked list. However, when I print the third linked list, it always prints 0 as the first value, followed by the correct sum values. Tried to debug and step through the AddTwoLists() function, but couldn't figure out where that 0 came from. I haven't included cases where the length of the two lists are different. Just trying to fix this problem first.

#include <iostream>

struct Node {
    int n; // number of non-zero values
    int index;
    int value;
    Node* link;
};

struct Data {
    int n;
    int index;
    int value;
};

Node* A;
Node* B;

void AddEndNode(Node*& head, int index, int value){
    Node* current = head;
    Node* temp = new Node;
    // temp->n = n;
    temp->index = index;
    temp->value = value;
    temp->link = NULL;
    
    if(current == NULL) head = temp;
    else{
        while(current->link != NULL) current = current->link;
        current->link = temp;
    }
}

void PrintList(Node* head){
    Node* current = head;
    
    while(current != NULL){
        std::cout<< current->value<< "\t";
        current = current->link;
    }
    std::cout<< "\n";
}

void AddTwoLists(Node* A, Node* B){
    Node* currentA = A;
    Node* currentB = B;
    Node* C = new Node;
    C->n = A->n;
    C->link = NULL;
    int sum = 0;
    int index = 1;
    
    while(currentA != NULL){
        sum = 0;
        C->index = index;
        sum += currentA->value;
        std::cout<< "\n1st sum is "<< sum;
        sum += currentB->value;
        std::cout<< "\n2nd sum is "<< sum;

        AddEndNode(C, index, sum);
        std::cout<< "\nlist C is ";
        PrintList(C);
        currentA = currentA->link;
        currentB = currentB->link;
        index++;
    }

    PrintList(C);
}


int main() {
    Data dataA, dataB;
    dataA.index = 1;
    dataB.index = 1;
    
    A = NULL;
    B = NULL;

    std::cout<< "How many non-zero whole numbers do you want to add to list A? \n";
    std::cin>> dataA.n;
    for(int i =0; i < dataA.n; i++){
        std::cout<< "Please enter a non-zero whole number: ";
        std::cin>> dataA.value;
        AddEndNode(A, dataA.index, dataA.value);
        dataA.index++;
    }
    PrintList(A);

    std::cout<< "\nHow many non-zero whole numbers do you want to add to list B? \n";
    std::cin>> dataB.n;
    for(int i =0; i < dataB.n; i++){
        std::cout<< "Please enter a non-zero whole number: ";
        std::cin>> dataB.value;
        AddEndNode(B, dataB.index, dataB.value);
        dataB.index++;
    }
    PrintList(B);
    
    std::cout<< "\nThe sum of listA and listB: \n";
    AddTwoLists(A, B);

    return 0;
}

test

Answer 1

Your code explicitly creates that node at the very start:

Node* C = new Node;

This is a dummy node that in some algorithms facilitates the rest of the code, but here it doesn't bring any benefit.

At the end this is still the first node of your C list, but as it is a dummy node, not based on any real data, it should not be included in the output.

Better is to apply the same principle you used for A and B: an empty list is represented with NULL (or better nullptr in C++), and you can do the same with C.

In conclusion: don't create a dummy node.

Other remarks

• Your code has undefined behaviour when the second input list is shorter than the first. In that case your loop will do currentB = currentB->link; when currentB was already a null pointer.

• The index member serves no purpose and goes against the advantages of linked lists, i.e. that you can easily insert or remove a node in the middle of the linked list. But this index member then becomes a stumbling block: after such alteration you have to renumber the index members of the remaining nodes in the list.

• The n member should not be stored in every node: it is a property that applies to the whole list. If you really want to store this, it should be stored in a separate structure that also has the head pointer to the list nodes. But if we just stick with the Node, then don't store n. It is not needed.

• Because of the previous two points you wouldn't need the Data structure either.

• AddEndNode is inefficient: the longer the list gets, the more time it will take to find the tail and append a node there. It is better to prefix the node, and when needed, reverse the list.

• AddToLists prints the result, but the caller of that function will not have the result. It is better to return the pointer to the new list and have the main function print the result.

• Don't define A and B as global variables. Declare them in main.

• Use camelCase for these function names and variables. So a instead of A and addTwoNodes instead of AddTwoNodes.

Here is the modification of your code with the above points taken into account:

#include <iostream>

struct Node {
    int value;
    Node* link;
};

void prefixNode(Node*& head, int value){
    Node* current = head;
    
    head = new Node;
    head->value = value;
    head->link = current;
}

void reverse(Node*& head) {
    Node *current = head;
    head = nullptr;
    while (current) {
        Node *next = current->link;
        current->link = head;
        head = current;
        current = next;
    }
}

void printList(Node* head){
    Node* current = head;
    
    while (current) {
        std::cout<< current->value<< "\t";
        current = current->link;
    }
    std::cout<< "\n";
}

Node* addTwoLists(Node* a, Node* b) {
    Node* c = nullptr;
    
    while (a || b) {
        int sum = 0;
        if (a) {
            sum += a->value;
            a = a->link;
        }
        if (b) {
            sum += b->value;
            b = b->link;
        }
        prefixNode(c, sum);
    }
    reverse(c);
    return c;
}


int main() {
    Node* a = nullptr;
    Node* b = nullptr;
    int n, value;
    
    std::cout<< "How many non-zero whole numbers do you want to add to list A? \n";
    std::cin>> n;
    for(int i = 0; i < n; i++) {
        std::cout<< "Please enter a non-zero whole number: ";
        std::cin>> value;
        prefixNode(a, value);
    }
    reverse(a);
    printList(a);

    std::cout<< "How many non-zero whole numbers do you want to add to list B? \n";
    std::cin>> n;
    for(int i = 0; i < n; i++) {
        std::cout<< "Please enter a non-zero whole number: ";
        std::cin>> value;
        prefixNode(b, value);
    }
    reverse(b);
    printList(b);
    
    std::cout<< "The sum of listA and listB: \n";
    Node *c = addTwoLists(a, b);
    printList(c);

    return 0;
}

More remarks

• It is not clear why the user is prompted to enter a non-zero number. There wouldn't be any special thing happening when the user enters zero. It just adds up like any other number would.

  Maybe this comes from an idea to use zero as a terminator. In that case the user would not have to first tell the system how many numbers they plan to enter, but could just start entering values and end the sequence with a zero that would not be stored in the list, but would just signal the end of the input for that list.

• There are similar exercises where two linked lists are to be added, but where the value in each node is limited to one digit. When the sum becomes 10 or more, only the least significant digit should be stored, and the remaining 1 should act as a carry over to the next sum.

• It was not clear how the list nodes should be aligned when the lists do not have the same length. In some exercises the alignment should be at the last node, not the first (like here). In any case you can deal with this by reversing the lists (or not).