LeetCode算法解题集：Add Two Numbers

题目：

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

思路：
同时循环两个链表，如果都不为空，则相加并加上次的进位值（0/1）,然后再判断是否进位；如果一个链表为空，则相加上次进位值（0/1）；如果都为空，则退出；最后判断最后一次是否有进位。算法复杂度：O(n),代码如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
void NewNode(ListNode **pCurPos, ListNode **pResultList, int num)
{
    if (*pCurPos == NULL)
    {
        *pResultList = new ListNode(num);
        *pCurPos = *pResultList;
    }
    else
    {
        ListNode *pNewNode = new ListNode(num);
        (*pCurPos)->next = pNewNode;
        *pCurPos = pNewNode;
    }
}
 
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *pResultList = NULL;
    ListNode *pCurPos = NULL;
 
    int need_carry = 0;
    ListNode *pCur1 = l1;
    ListNode *pCur2 = l2;
 
    while (pCur1 != NULL || pCur2 != NULL)
    {
        if (pCur1 != NULL && pCur2 != NULL)
        {
            int sum = pCur1->val + pCur2->val + need_carry;
            need_carry = sum / 10;
            sum = sum {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c} 10;
 
            NewNode(&pCurPos, &pResultList, sum);
        }
        else if (pCur1 == NULL && pCur2 != NULL)
        {
            int sum = pCur2->val + need_carry;
            need_carry = sum / 10;
            sum = sum {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c} 10;
             
            NewNode(&pCurPos, &pResultList, sum);
        }
        else if (pCur1 != NULL && pCur2 == NULL)
        {
            int sum = pCur1->val + need_carry;
 
            need_carry = sum / 10;
            sum = sum{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}10;
 
            NewNode(&pCurPos, &pResultList, sum);
        }
 
        if (pCur1 != NULL)
        {
            pCur1 = pCur1->next;
        }
 
        if (pCur2 != NULL)
        {
            pCur2 = pCur2->next;
        }
    }
 
    if (need_carry != 0)
    {
        NewNode(&pCurPos, &pResultList, need_carry);
    }
 
    return pResultList;
}
 
};

总结：
1、该题本身不是特别难，思路很简单，考察的仅是链表的应用。
2、算法效率跟语言有很大关系。

比如官方的图片如下，同样的算法，不同的语言，效率真的会差很多。c > c++ > python > c# > javascript > java

本文摘录于海阔天空的博客，作者: zjg555543，发布时间: 2015-07-08