LeetCode——两数相加

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

一、CPP链表遍历相加

解题思路：思路很简单，就是一起遍历两个链表，把其值加起来，使用尾插法插入一个新的链表（因为本来两个链表就是逆序的，而且得出的结果也是逆序的）。当其中的一个链表为NULL时，就单独处理另一个链表。
注意：两个链表的值加起来可能大于10，所以需要注意进位问题，特设一个flag来表示是否有进位。
时间复杂度：O(max(m,n))，m，n分别是两个链表的长度。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int sum = 0;
        int flag = 0;         //初始化flag为0
        ListNode* head= new ListNode(0);
        ListNode* p = head;
        while(l1&&l2){
            sum = l1->val + l2->val + flag;   //计算两数之和
            flag = sum >= 10 ? 1 : 0;         //确定flag的值（个数相加不会大于20，故flag为1或0）
            l1 = l1->next;
            l2 = l2->next;
            ListNode* newnode = new ListNode(sum%10);  //使用尾插法，将新结点插入链表
            p->next = newnode;
            p = p->next;
        }
        //单独处理l1剩余部分
        while(l1){
            sum = l1->val + flag;
            flag = sum >= 10 ? 1 : 0;
            ListNode* newnode = new ListNode(sum%10);
            p->next = newnode;
            p = p->next;
            l1 = l1->next;
        }
        //单独处理l2剩余部分
        while(l2){
            sum = l2->val + flag;
            flag = sum >= 10 ? 1 : 0;
            ListNode* newnode = new ListNode(sum%10);
            p->next = newnode;
            p = p->next;
            l2 = l2->next;
        }
        //最终flag为1则需要进位一个单独的“1”，为1的情况只能是从第一个whlie循环跳出直接到这
        if(flag){
            ListNode* newnode = new ListNode(1);
            p->next = newnode;
            p = p->next;
        }

        return head->next;
    }
};

扩展解法：上面的做法是在不确定两个链表的长度的情况下，先以短的为基准，处理共同部分，然后再处理另一个较长的。也可以刚一开始就把两个链表的长度扩展成一样长，把短的那个后面补0。

简单但超出时间限制的做法：上面的做法，当单独处理其中一个链表时，还是用尾插法的方式，也可以把长的链表剩余的部分直接连接在新的链表后面，但是这种方法超过了时间的限制，如下。

 while(l1)
        {
            r->next = l1;
        }
 while(l2)
      {
            r->next = l2
      }

结构体知识点：结构体也可以使用new来创建新的节点，还可以在结构体中使用初始化列表定义构造函数，如下：

#include<iostream>
#include<cstdlib>

using namespace std;

int main()
{
    
    struct ListNode {
     int val;
     ListNode *next;
     //初始化列表定义结构体的构造函数
     ListNode(int x) : val(x), next(NULL) {}  
    };

    ListNode* head = new ListNode(1);

    cout<<head->val;
    cout<<head->next;

    return 0;
}

上面输出为1，0。如果不定义构造函数，直接使用ListNode* head = new ListNode();来new一个Node，那么输出将为0 ，0。还可以使用malloc动态创建struct node，下面这个例子输出也为1，0。

#include<iostream>
#include<cstdlib>

using namespace std;

int main()
{
    
    struct ListNode {
     int val;
     ListNode *next;
    };

    ListNode* head;

    head = (ListNode *)malloc(sizeof(ListNode));
    head->next = NULL;
    head->val = 1;

    cout<<head->val;
    cout<<head->next;


    return 0;
}

二、Java链表遍历相加

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

         if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        int flag= 0;
        ListNode res = new ListNode(-1);
        ListNode tmp = res;
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + flag;
            res.next = new ListNode(sum % 10);
            res = res.next;
            jinwei = sum / 10;
            l1 = l1.next;
            l2 = l2.next;

        }
        while (l1 != null) {
            int sum = l1.val + flag;
            res.next = new ListNode((sum) % 10);
            res = res.next;
            jinwei = sum / 10;
            l1 = l1.next;

        }
        while (l2 != null) {
            int sum = l2.val + flag;
            res.next = new ListNode((sum) % 10);
            res = res.next;
            jinwei = sum / 10;
            l2 = l2.next;

        }
        if (flag) {
            res.next = new ListNode(1);
        }
        return tmp.next;

    }
}

三、Python链表遍历相加（补位法）

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        re = ListNode(0)
        r=re
        flag=0
        while(l1 or l2):
            x= l1.val if l1 else 0
            y= l2.val if l2 else 0
            s=flag+x+y
            flag=s//10
            r.next=ListNode(s%10)
            r=r.next
            if(l1!=None):l1=l1.next
            if(l2!=None):l2=l2.next
        if(flag>0):
            r.next=ListNode(1)
        return re.next

四、各语言及算法时间复杂度

各语言及算法时间复杂度