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