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

Question

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

我正在考虑使用stack解决问题.我将遍历两个列表并将数据元素推送到两个单独的堆栈中.每个链接列表.然后我将两个堆栈弹出并添加两个元素,如果结果是两位数没有I 10对其进行模数化并将进位存储在临时变量中.余数存储在节点中,并将进位加到下一个总和中,依此类推.如果两个堆栈是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; 

我在面试问题中多次遇到过这个问题,但这是我能想到的最好的解决方案.如果有人能在ci中找到更高效的东西,那将非常高兴.

Answer 1

两次传球,没有筹码:

• 获取两个列表的长度.

• 使用一个节点创建解决方案列表.将此节点的值初始化为零.这将保持进位数.将列表指针(称为进位指针)设置为此节点的位置.将列表指针(称为结束指针)设置为此节点的位置.

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

• 现在我们留下两个列表指针,每个列表指针具有相同数量的节点.

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

  • 将新节点链接到结束指针并将结束指针前进到此节点.

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

  • 将两个值一起添加.

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

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

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

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

Answer 2

这就是我要解决这个问题的方法:

第1步:在两个链接列表上传递,查找长度

说 len(L1) = m and len(L2) = n

第2步:找出长度差异

if ( m > n )
    d = m - n
else if ( n > m )
    d = n - m
else
    d = 0

步骤3:将临时指针d移到较大列表之前

第4步:现在我们有两个链接列表要添加其长度相同,所以递归添加它们,保持进位.

步骤5: (注:如果(d == 0)不执行此步骤)

在第4步之后,我们有了部分输出列表,现在我们必须将更大的列表的剩余部分放在输出列表的开头.

if ( d > 0 )
    -Travel larger list till d positions recursively
    -Append sum = value_at_end + carry (update carry if sum >= 10) to output list at beginning
    -Repeat until difference is consumed

注意:我正在解决问题,因为它摆在我面前,而不是建议基础数据结构的变化.

时间复杂度:

1. 在两个列表上进行单次传递以查找其长度: O(m+n)
2. 递归地对两个相同大小(m - d和n)的链表进行求和:O(n)假设m > n
3. 将剩余的较大列表附加到输出列表: O(d)

总计:O( (m+n) + (n) + (d) )或O(m+n)

空间复杂度:

1. 时间复杂度的第2步:O(n),运行时堆栈空间
2. 时间复杂度的第3步:O(d),运行时堆栈空间

总计:O(n + d)或O(n)