给定一种链表，里面每个节点里都有一个0-9的数字，用来表示一个超大数

请设计程序做两个链表的加法运算。

比如：

9>9>9>NULL + 1>NULL =>  1>0>0>0>NULL

链表数据结构：

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

struct List
{
 Node* head;
 int length; /* 长度 */
};

肯定是使用递归啦，不然没办法解决进位+1问题，因为这时候要让前面的节点加1，而我们的单链表是永远指向前的，

此外对于999+1=1000，新得到的值的位数（4位）比原来的两个值（1个1位，1个3位）都多，所以我们将表头的值设置为0，如果多出一位来，就暂时存放到表头。递归结束后，如果表头为1，就在新的链表外再加一个新的表头。

//head1 length > head2, so M > N
public static int Add(Link head1, Link head2, ref Link newHead, int M, int N)
{
    // goto the end
    if (head1 == null)
        return 0;

    int temp = 0;
    int result = 0;

    newHead = new Link(null, 0);

    if (M > N)
    {
        result = Add(head1.Next, head2, ref newHead.Next, M - 1, N);

        temp = head1.Data + result;
        newHead.Data = temp % 10;

        return temp >= 10 ? 1 : 0;
    }
    else // M == N
    {
        result = Add(head1.Next, head2.Next, ref newHead.Next, M - 1, N - 1);

        temp = head1.Data + head2.Data + +result;
        newHead.Data = temp % 10;

        return temp >= 10 ? 1 : 0;
    }
}

这里假设head1比head2长，而且M、N分别是head1和head2的长度。

还有一种就是双链表了，确实不用递归。

凑字数

1: reverse
2: loop: r = a + b + c
3: reverse