c - 在 C 中有效地添加两个链表

Question

我有两个链表，按照从最重要到最不重要的顺序表示十进制数字的数字。例如 4->7->9->6 和 5->7 答案应该是 4->8->5->3 且不反转列表，因为反转列表会导致效率降低。

我正在考虑使用堆栈解决问题。我将遍历两个列表并将数据元素插入两个单独的堆栈。每个链表一个。然后我将两个堆栈弹出到一起并添加两个元素，如果结果是一个两位数 no I 10 modulo it 并将进位存储在临时变量中。余数存储在节点中，进位被添加到下一个和等等。 如果两个栈是s1和s2，结果链表是res。

temp = 0;
res = (node*)(malloc(sizeof(node*));

while(s1->top!=-1 || s2->top!=-1)
{  
    temp = 0;
    sum = pop(s1) + pop(s2);
    n1 = (node*)(malloc(sizeof(node*));
    temp = sum/10;
    sum = sum%10;
    sum = sum+temp;
    n1->data = sum;
    n1->next = res;
    res = n1;
    free n1;
    //temp=0;
}

if((s1->top==-1)&&(s2->top==-1))
{
    return res;
}
else if(s1->top==-1)
{
    while(s2->top!=-1)
    {
        temp = 0;
        sum = pop(s2);
        sum = sum + temp;
        temp = sum/10;
        sum = sum%10;
        n1 = (node*)(malloc(sizeof(node*));
        n1->data = sum;
        n1->next = res;
        res = n1;
        free n1;
    }
}
else
{
    while(s2->top!=-1)
    {
        temp = 0;
        sum = pop(s2);
        sum = sum+temp;
        temp = sum/10;
        sum = sum%10;
        n1=(node*)(malloc(sizeof(node*));
        n1->data = sum;
        n1->next = res;
        res = n1;
        free n1;
    }
}

return res; 

我在面试题中多次遇到过这个问题，但这是我能想到的最好的解决方案。 如果有人能在 c 中提供更高效的东西，我将非常高兴。

Answer 1

两次通过，没有堆栈:

• 获取两个列表的长度。

• 创建一个包含一个节点的解决方案列表。将此节点的值初始化为零。这将保留进位数字。将列表指针(称为进位指针)设置为该节点的位置。将列表指针(称为结束指针)设置为该节点的位置。

• 从较长的列表开始，对于每个多余的节点，将一个新节点链接到结束指针并为其分配多余节点的值。将结束指针设置为这个新节点。如果 值小于9，将进位指针指向新节点。

• 现在我们剩下的两个列表指针都具有相同数量的节点。

• 虽然列表不是空的...

  • 将一个新节点链接到结束指针并将结束指针推进到该节点。

  • 从每个列表中获取值并将每个列表指针推进到下一个节点。

  • 将两个值相加。

    1. 如果值大于九，将值设置为value mod 10，增加进位指针节点中保存的值，将进位指针移动到下一个节点。如果进位指针的值为 9，则设置为零并转到下一个节点。

    2. 如果值为 9。设置它。什么都不做。

    3. 如果值小于九。设置它。将进位指针设置为当前节点。

• 完成两个列表后，检查解决方案指针的节点值是否为零。如果是，则将解决方案指针设置为下一个节点，删除不需要的额外数字。