【LeetCode_C++_Day2_两数相加（详解）】

LeetCode2_两数相加

1.题目描述：

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

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

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

示例：

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

题目分析

本题不难，算法比较简单，只是简单的考察对链表的运用是否熟练。 两个链表，只需将对应的位置相加，注意进位，注意截止点即可。下面给出几种解法，附加相关代码分析：

注：leetcode给出结构体声明：

 //Definition for singly-linked list.
 struct ListNode 
 {
     int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
 };

解法1：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
       ListNode *l3=NULL;
       int y=0;//用于记录相应位置上的进位
       int x=0;//用于记录相应位置上的额最终数据
       int num;//用于记录每一位上的和
       ListNode *l4,*cur=NULL;
       while(l1!=NULL||l2!=NULL)
       {
           if(l1==NULL)//用if和else考虑当一个链表到达终点而另一个没有到达终点的情况
           {
               num=(l2->val+y);
               x=num%10;
               y=num/10;
                l2=l2->next;

           }
           else if(l2==NULL){
               num=(l1->val+y);
                x=num%10;
                y=num/10;
                l1=l1->next;
           }
           else//用于分析正常相加的部分
           {
               num=(l1->val+l2->val+y);
               x=num%10;
               y=num/10;
               l1=l1->next;
               l2=l2->next;
           }
       //以上两个判断执行的是找出最终的尾数上的值x
       //接下来将得到的x的值赋值给对应的结点
           if(l3==NULL)//这一部分是头结点的建立
           {
               l4 = new ListNode(x);
               l3 = l4;
               cur = l4;
           }
           else{
           //有了头结点以后的赋值
                l4 = new ListNode(x);
                cur->next = l4;//先把后一个结点和前一个挂起来
                cur=l4;//然后现在结点这个标记后移
           } 
       }
       if(y>0)
       //while循环之后又放了一个if
       //之所以还有这一个if，是当两个加数链表均为空以后，多出的进位需要单独占位
       {
            l4 = new ListNode(y);
            cur->next = l4;
            cur=l4;
       }
     return l3;
    }
};

代码思路总述：

1）循环中分为两个部分，第一个部分用于得到最终的和的相应位数应当保留的最终数值x，另外一个部分负责建立链表，将第一部分得到的x赋值给新的结点；
2）循环完成之后再添加一个if，用于将两个加数链表均结束，但是进位上依然有的值添加一个结点添加到链表上

解法2.1：

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int c=0;
    struct ListNode *head=(struct ListNode *)malloc(sizeof(struct ListNode)),*cur=head,*del=head;
    //head虚拟头结点地址,cur当前节点地址,del用于删除虚拟头结点
    //设置虚拟头结点:为防止内存泄露,虚拟头结点需删除
    while(l1!=NULL||l2!=NULL||c)
    {
        cur->next=(struct ListNode *)malloc(sizeof(struct ListNode));
        cur=cur->next;//这里跳过了头结点，头结点没用，需要释放
        l1=l1!=NULL?(c+=l1->val,l1->next):l1;
        l2=l2!=NULL?(c+=l2->val,l2->next):l2;
        cur->val=c%10;//此时的c是上一数位的进位加上本数位数字和
        c=c/10;//c是进位
    }
    cur->next=NULL;//尾指针为空
    head=head->next;//准备释放头结点
    free(del);//最开始两个标记指向这一块内存，一个head 标记后移之后还可以通过del释放内存，防止内存泄漏
    return head;
}

代码亮点难点分析:

1.三目运算符的使用

l1=l1!=NULL?(c+=l1->val,l1->next):(c+=0,l1);
l2=l2!=NULL?(c+=l2->val,l2->next):(c+=0,l2);

（判断式）？（判断式正确时执行的表达式）：（判断式不正确时返回的表达式）

l1不为空,说明当前位还有值,则加l1当前位的值,l1地址指向下一位
l1为空,说明l1加完了,就给进位加0(不变),l1始终不变指向空
l2同理,直到l1,l2都为空,c为0停止
此处两条三目表达式并列进行，就可以，如果其中一个加数链表结束也无妨，代替解法1中的if。
不成立时用l1=l1这种废话来跳过，也挺好！！

2.while中条件

while(l1!=NULL||l2!=NULL||c){}

代码执行条件比较宽松，原因还是三目运算符中的精彩使用

解法2.2:

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int c=0;
    struct ListNode *head=(struct ListNode *)malloc(sizeof(struct ListNode)),*cur=head;
    while(cur!=NULL)//条件也可以写l1!=NULL||l2!=NULL||c
    {
        l1 = (l1 != NULL) ? (c += l1->val, l1->next) : l1;
        l2 = (l2 != NULL) ? (c += l2->val, l2->next) : l2;
        cur->val = c % 10;//以上部分在第一次循环中均是先对头结点点操作，头结点有意义，无须释放
        c /= 10;
        cur->next = (l1!=NULL || l2!=NULL || c!=0)?(struct ListNode *)malloc(sizeof(struct ListNode)) : NULL;
        cur = cur->next;
    }
    return head;
}

注：与解法2.1的区别：第一次循环的顺序不同

2.1先跳过头结点再操作，头结点无意义，需释放；
2.2先操作，在申请结点空间，头结点有意义，无须释放

解法3：递归

int c=0;
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    if(l1==NULL && l2==NULL && c==0)return NULL;.//终止条件
    l1 = l1!=NULL ? (c += l1->val, l1->next) : l1;
    l2 = l2!=NULL ? (c += l2->val, l2->next) : l2;
    struct ListNode *cur = (struct ListNode *)malloc(sizeof(struct ListNode));
    cur->val = c%10;
    c /= 10;
    cur->next = addTwoNumbers(l1,l2);//亮点难点
    return cur;
}

本解法递归讲解：

递归当然包括“递”的过程和“归”的过程，中间有一个截止条件：
1）递：每一次递的对象：一个链表 向 与本链表相比少了一个操作结点的上一层链表传递：

2）截止条件： 不断地传递过程中链表的长度不断减少，截止条件是当返回当链表的长度为零；链表什么时候长度为零呢？当加数链表长度都截止，并且进位均为零时截止；

3）归：每一个链表有比他少一个结点的链表加上一个结点构成；

递归如图：

本人能力有限，但也希望能对入门学习的朋友有所帮助，如果发现文中理解有错误，恳请留言提出！

					            			 					2020/05/05