无法使用链接列表添加两个数字

Question

我正在尝试将存储为链接列表的两个数字相加。

在下面的代码中，指向每个数字的第一个数字的指针被传递给方法 addListNumbers() 方法。这会调用 addNumbers() 方法来添加每个数字的 k 个最低有效位，并调用 addRemaining() 方法来添加较大数字的剩余数字数量。

#include <stdio.h>
#include <stdlib.h>

struct Node{
    int data;
    struct Node *next;
};

struct Node* addNode(struct Node* head, int data){
    struct Node *node = (struct Node*)malloc(sizeof(struct Node));
    node->data=data;
    if(head!=NULL)
        head->next=node;
    node->next=NULL;
    return node;
}

void addRemaining(struct Node *num1, struct Node **result, int *carry, int diff){
    int sum=0;
    if(!num1||diff==0)
        return;
    addRemaining(num1->next, result, carry, diff-1);
    sum=num1->data+*carry;
    *carry=sum/10;
    sum=sum%10;
    struct Node *temp=(struct Node *)malloc(sizeof(struct Node));
    temp->data=sum;
    temp->next=*result;
    *result=temp;   
    return;
}

void addNumbers(struct Node *num1, struct Node *num2, struct Node **result, int *carry){
    int sum;
    if(!num1)
        return;
    addNumbers(num1->next, num2->next,result,carry);
    struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    // printf("sum=num1->data+num2->data+(*carry)----- %d",*carry);
    sum=num1->data+num2->data+(*carry);
    // printf("sum is:%d ",sum);
    *carry=sum/10;
    // printf("carry is:%d ",*carry);
    sum=sum%10;
    temp->data=sum;
    temp->next=*result;
    *result=temp;
    return;
}

void addListNumbers(struct Node *num1, struct Node *num2, struct Node **result, int *carry){
    int l1Length=0, l2Length=0, diff=0;
    struct Node *current=num1;
    while(current!=NULL){
        current=current->next;
        l1Length++;
    }
    current=num2;
    while(current!=NULL){
        current=current->next;
        l2Length++;
    }
    if(l1Length<l2Length){
        current=num1;
        num1=num2;
        num2=current;
    }
    diff=abs(l1Length-l2Length);
    current=num1;
    while(diff){
        current=current->next;
        diff--;
    }
    addNumbers(current, num2, result, carry);
    diff=abs(l1Length-l2Length);
    addRemaining(num1, result, carry, diff);
    // if(*carry){
    //     struct Node *temp=(struct Node*)malloc(sizeof(struct Node));
    //     temp->next=*result;
    //     temp->data=temp->data+*carry;
    //     *result = temp;
    // }
}

void printList(struct Node* list){
    struct Node *current=(struct Node *)malloc(sizeof(struct Node));
    current=list;
    if(current==NULL)
        return;
    printf("%d", current->data);
    printList(current->next);
}

int main(){
    struct Node *num1 = addNode(NULL,6);
    struct Node *n2 = addNode(num1,2);
    struct Node *n3 = addNode(n2,7);
    // struct Node *n4 = addNode(n3,4);
    // struct Node *n5 = addNode(n4,5);
    printf("Num 1:: ");
    printList(num1);
    printf("\n");
    struct Node *num2 = addNode(NULL,8);
    struct Node *n22 = addNode(num2,1);
    struct Node *n23 = addNode(n22,6);
    struct Node *n24 = addNode(n23,4);
    struct Node *n25 = addNode(n24,7);
    printf("Num 2:: ");
    printList(num2);
    printf("\n");
    struct Node *result=(struct Node*)malloc(sizeof(struct Node));
    int carry=0;
    addListNumbers(num1, num2, &result, &carry);
    printf("After Adding:");
    printList(result);
    printf("\n");
    return 0;
}

这两个数字相加很好，但结果末尾还有一个零。对于上面添加的两个数字，它会产生以下输出:

Num 1:: 627
Num 2:: 81647
After Adding:822740

而实际答案是 82274。

感谢任何帮助:)

Answer 1

您的函数 addNumbers 递归地计算 2 位数字的总和，并将结果放在通过 result 参数访问的列表前面。在调用 addListNumbers 之前，您已经通过为第一个节点分配内存为结果列表准备了初始最后一位数字:

struct Node *result=(struct Node*)malloc(sizeof(struct Node));
...
addListNumbers(num1, num2, &result, &carry);

您未能设置result->next = NULL，但意外的是您分配的节点被零填充。这可以防止您出现 SEGFAULT 等问题。一般来说，您应该初始化正确分配的内存。但在这种情况下，您根本不应该分配任何内容，而应将 result 设置为 NULL。

顺便说一句:在 printList 中，您为链接列表的副本分配内存。此后不再使用它并导致内存泄漏。无需在该函数中分配任何内容。只需使用 list 而不是 current。