添加两个表示为链接列表的大数字,而不反转链接列表

Question

假设您有2个大数字表示为链表,您如何添加它们并将结果存储在单独的链表中.例如

a = 2 -> 1 -> 7 
b = 3 -> 4
result = 2 -> 5 -> 1

你可以在不反转链接列表的情况下添加它们

Answer 1

伪代码:
步骤1.遍历链表并将元素推送到两个不同的堆栈中
步骤2.弹出堆栈中的顶部元素
步骤3.添加元素(+以前添加的任何进位)并将进位存储在临时变量中
步骤4.使用sum创建一个节点,并将其插入结果列表的开头

Answer 2

我认为这是超出背景的东西,但对于最初发布此问题的人来说可能是非常好的表现.

所以这是一个建议:

而不是将每个节点用作数字的单个数字,使用每个节点存储一个大数字(接近整数的大小),如果您选择存储在每个节点中的最高可能数字是x(您的情况9)那么您可以查看您的号码作为代表base x+1.其中每个数字是0到x之间的数字.

这将为您带来显着的性能提升,因为算法将在O(log n)时间内运行,并且在您的情况下需要与O(n)相同的节点数,n是两个加数中较大者的小数位数.

通常,为了便于您的算法,您可以选择10的幂作为适合整数范围的基数.

例如,如果您的号码是1234567890987654321并且您想将其存储在链接列表中,选择基数为10 ^ 8,那么您的表示应如下所示:

87654321-> 4567890 - > 123(小端)

Answer 3

/* 剧透：只需简单的递归即可 */

#include <stdio.h>

struct list {
    struct list *next;
    unsigned value;
    };
struct list a[] = { {NULL, 2} , {NULL, 1} , {NULL, 7} };
struct list b[] = { {NULL, 3} , {NULL, 4} };

unsigned recurse( unsigned * target, struct list *lp);
unsigned recurse( unsigned * target, struct list *lp)
{
    unsigned fact;
    if (!lp) return 1;
    fact = recurse (target, lp->next);

    *target += fact * lp->value;
    return 10*fact;
}

int main (void)
{
    unsigned result=0;

    /* set up the links */
    a[0].next = &a[1];
    a[1].next = &a[2];
    b[0].next = &b[1];

    (void) recurse ( &result, a);
    (void) recurse ( &result, b);

    printf( "Result = %u\n" , result );

return 0;
}