单链表表示的大数相加问题

记录下来怕自己忘记

问题描述：

2个单链表（singly linked list），每一个节点里面一个0-9的数字，输入就相当于两个大数了。然后返回这两个数的和（一个新list）。这两个输入的list 长度相等。 要求是：1. 不用递归。2. 要求算法在最好的情况下，只遍历两个list一次，最差的情况下两遍。

条件： 从高到低位存储大数。空间复杂度O(1)

记两个单链表分别为a,b; 长度为n? ，存储结构的单链表为c

分析：因为要求只能遍历list最多两次，且不能回头，所以只能是使用指针来记录因为进位而导致值更改的位置了~

a，b对应节点之和的情况只有3中，sum <9,sum = 9,sum >9

<9 时，直接赋值，当前指针pc前进，记录指针p也前进

= 9 时，要注意，意味着记录指针p不能移动（此时p指向的是<9的节点），pc前进

>9时，意味着要进位，从p到pc间的所有节点更新值。

因为进位而导致值修改，只能是值+1，此处安放一个指针。

?

伪代码如下：

//初始化一个单链表c，长度n+1 ，节点初始值为0#。。。。其实应该边算边new 节点的哈……

linkedlist? c = new linkedlist（n+1,0）

node * p = c.head,*pc = c.head

node * pa = a.head,*pb = b.head

pc = pc->next

while(pc)

?????sum = pa->value +pb->value

???? if? sum < 9

?????????? pc->value = sum

?????????? p = pc

?????????? pc = pc->next

?? else if sum ==9

?????????? pc = pc->next

??? else

????????????pc->value = sum%10

??????????? p->value?= p->value +1

??????????? do????????????????????

?????????????????? ?p = p->next

??????????????????? p->value = 0

???????????? while(p->next != pc);

#endwhile?????????

if c.head->value ==0

?????? node *tmp = c.head

???????c.head = c.head->next

?????? delete *tmp

?

?例如

a:??? 4?? 4? 4?? 4?? 0

b:??? 5?? 5?? 5?? 8?? 1

c:?x ?9?? 9? 9?? 12?

???p????????????? ?? pc