给定一种链表，里面每个节点里都有一个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

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

题目中链表节点只存[0, 10)，而且还给出了长度，那么问题就相对比较简单了。这里给出非递归解法：

#include <iostream>

using namespace std;

struct Node 
{
    int val; 
    Node *next;
    struct Node(int _val = 0, Node* _next = NULL)
        : val(_val), next(_next)
    {
    }
};

struct List
{ 
    Node* head; 
    int length; /* 长度 */
    List()
    {
        head = NULL;
        length = 0;
    }
    List& Reverse()
    {
        Node* newHead = NULL;
        while(head != NULL)
        {
            Node* tmpNode = head->next;
            head->next = newHead;
            newHead = head;
            head = tmpNode;
        }
        head = newHead;
        return *this;
    }
};
List Add(List& list1, List& list2)
{
    list1.Reverse();
    list2.Reverse();
    List list3;
    Node* head1 = list1.head, *head2 = list2.head, *head3 = NULL;
    int carry = 0;
    while(head1 != NULL || head2 != NULL || carry > 0)
    {
        int sum = carry;
        if(head1 != NULL)
            sum += head1->val;
        if(head2 != NULL)
            sum += head2->val;
        Node* tmpNode = new Node(sum % 10, head3);
        head3 = tmpNode;
        carry = sum / 10;
        if(head1 != NULL)
            head1 = head1->next;
        if(head2 != NULL)
            head2 = head2->next;
        list3.length++;
    }
    list1.Reverse();
    list2.Reverse();
    list3.head = head3;

    return list3;
}

int main()
{
    List list1, list2;
    Node* head1 = NULL, *head2 = NULL, *tmpNode = NULL;
    for(int i = 0; i < 3; i++)
    {
        tmpNode = new Node(9, head1);
        head1 = tmpNode;
    }
    list1.head = head1;
    list1.length = 3;
    for(int i = 0; i < 3; i++)
    {
        tmpNode = new Node(9, head2);
        head2 = tmpNode;
    }
    tmpNode = new Node(1, head2);
    head2 = tmpNode;
    list2.head = head2;
    list2.length = 4;

    List list3 = Add(list1, list2);
    tmpNode = list3.head;
    while(tmpNode != NULL)
    {
        cout <<tmpNode->val << " ";
        tmpNode = tmpNode->next;
    }

    // 资源释放就不写了

    return 0;
}

又写了一个比较丑的递归的

#include <iostream>

using namespace std;

struct Node 
{
    int val; 
    Node *next;
    struct Node(int _val = 0, Node* _next = NULL)
        : val(_val), next(_next)
    {
    }
};

struct List
{ 
    Node* head; 
    int length; /* 长度 */
    List()
    {
        head = NULL;
        length = 0;
    }
};

// 返回值代表是否有进位，0代表没有进位，1代表有一位进位
// 最后一个参数newHead为加法后的链表头结点
void Add(Node* head1 , int len1, Node* head2, int len2, Node*& newHead, int& len)
{
    if(len1 == 0 && len2 == 0)
        return;
    if(len1 < len2)
        return Add(head2, len2, head1, len1, newHead, len);
    Node* tmpNode = NULL;
    if(len1 == len2)
    {
        Add(head1->next, len1 - 1, head2->next, len2 - 1, newHead, len);
        if(len < len1)
        {
            int tmpVal = head1->val + head2->val;
            for(int i = 0; i < 2; i++)
            {
                if(tmpVal == 0)
                    break;
                tmpNode = new Node(tmpVal % 10, newHead);
                newHead = tmpNode;
                ++len;
                tmpVal /= 10;
            }
        }
        else
        {
            int tmpVal = head1->val + head2->val + newHead->val;
            newHead->val = tmpVal % 10;
            tmpVal /= 10;
            if(tmpVal > 0)
            {
                ++len;
                tmpNode = new Node(tmpVal, newHead);
                newHead = tmpNode;
            }
        }
    }
    else
    {
        Add(head1->next, len1 - 1, head2, len2, newHead, len);
        if(len < len1)
        {
            Node *tmpNode = new Node(head1->val, newHead);
            newHead = tmpNode;
            ++len;
        }
        else
        {
            int tmpVal = newHead->val + head1->val;
            newHead->val = tmpVal % 10;
            tmpVal /= 10;
            if(tmpVal > 0)
            {
                tmpNode = new Node(tmpVal % 10, newHead);
                newHead = tmpNode;
                ++len;
            }
        }
    }
}

void Add(const List& list1, const List& list2, List& list3)
{
    Add(list1.head, list1.length, list2.head, list2.length, list3.head, list3.length);
}

int main()
{
    List list1, list2;
    Node* head1 = NULL, *head2 = NULL, *tmpNode = NULL;
    for(int i = 0; i < 3; i++)
    {
        tmpNode = new Node(9, head1);
        head1 = tmpNode;
    }
    list1.head = head1;
    list1.length = 3;
    for(int i = 0; i < 3; i++)
    {
        tmpNode = new Node(9, head2);
        head2 = tmpNode;
    }
    tmpNode = new Node(1, head2);
    head2 = tmpNode;
    list2.head = head2;
    list2.length = 4;

    List list3;
    Add(list1, list2, list3);
    tmpNode = list3.head;
    while(tmpNode != NULL)
    {
        cout <<tmpNode->val << " ";
        tmpNode = tmpNode->next;
    }
    cout << endl;

    // 资源释放就不写了

    return 0;
}