2.两数相加

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

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

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

示例：

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

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) { ListNode p = l1; //将运算结果保存在l1中 ListNode q = l2; int addNum = 0; //表示进位数 while(q!=null){ //所以以l2遍历为主按值计算 if(p.next==null && q.next!=null) // 用于判定链表的结束标志 p.next = new ListNode(0); if(q.next==null && p.next!=null)// 用于判定链表的结束标志 q.next = new ListNode(0); int sumAll = addNum + p.val + q.val; p.val = sumAll % 10; //表示本位数保存 addNum = sumAll / 10; //用于表示进位数参与下一位数的本位计算 if(p.next == null && q.next == null && addNum!=0) p.next = new ListNode(addNum); //用于结果链的结尾置零，表示尾空 p = p.next; q = q.next; } return l1; } }

Java题解2

class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode p = l1, q = l2, curr = dummyHead; int carry = 0; while (p != null || q != null) { int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; int sum = carry + x + y; carry = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; if (p != null) p = p.next; if (q != null) q = q.next; } if (carry > 0) { curr.next = new ListNode(carry); } return dummyHead.next; } }

C题解：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ void deeltail(struct ListNode * pre,struct ListNode * r,int carry); struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode * head ,*p,*q,*pre; int carry = 0; if(l1 == NULL) return l2; if(l2 == NULL) return l1; head = l1; p = head; while(l1 && l2){ pre = p;//指向p指针的前向指针 p->val = l1->val + l2->val + carry; carry = 0; if(p->val > 9){ p->val -= 10; carry = 1; } l1 = l1->next; l2 = l2->next; p = p->next; } if(!l1 && !l2){//l1与l2都只有一个数 if(carry){ q= (struct ListNode *)malloc(sizeof(struct ListNode)); q->val = carry; q->next = NULL; pre->next = q; } } else if(l2){//l1的长度小于l2,由于head最初是指向l1的，特殊处理 deeltail(pre,l2,carry); } else{//l1的长度大于l2 deeltail(pre,l1,carry); } return head; } void deeltail(struct ListNode * pre,struct ListNode * r,int carry){ struct ListNode * q; pre->next = r; q = pre->next; while(q){ q->val +=carry; if(q->val>9){ q->val -= 10; carry = 1; }else{ carry =0; } pre = q; q = q->next; } if(carry){//最后一个节点加上进位大于10需处理多出来的节点，val=1 q= (struct ListNode *)malloc(sizeof(struct ListNode)); q->val = carry; q->next = NULL; pre->next = q; } }

C语言题解2：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode *new1,*p3; static struct ListNode *result; result=(struct ListNode *)malloc(sizeof(struct ListNode)); result->next=NULL;//这里很重要，定义了指针以后，要把它的next赋成NULL，否则会编译出错 int sum=0; p3=result; while(1) { if(l1) { sum+=l1->val; l1=l1->next; } if(l2) { sum+=l2->val; l2=l2->next; } p3->val=sum%10; sum=sum/10; if(l1 || l2 || sum!=0)//当l1不为空或l2不为空或sum不为0时，循环继续 { new1=(struct ListNode *)malloc(sizeof(struct ListNode)); new1->next=NULL;//这里很重要，定义了指针以后，要把它的next赋成NULL，否则会编译出错 p3->next=new1; p3=p3->next; } else break;//否则跳出循环得到结果 } return result; }

C题解3：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode *p1 = l1; struct ListNode *p2 = l2; struct ListNode *l3 = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode *p3 = l3; int carry = 0; int sum = 0; while( p1 != NULL&& p2 != NULL) { sum = p1->val + p2->val + carry; if(sum>9) { sum%=10; carry = 1; } else { carry = 0; } struct ListNode *p4 = (struct ListNode*)malloc(sizeof(struct ListNode)); p4->val = sum; p4->next = NULL; p3->next = p4; p3 = p4; p1 = p1->next; p2 = p2->next; } while(p1!=NULL)//p1较长 { sum = p1->val + carry; if(sum>9) { sum%=10; carry = 1; } else { carry = 0; } struct ListNode *p5 = (struct ListNode*)malloc(sizeof(struct ListNode)); p5->val = sum; p5->next = NULL; p3->next = p5; p3 = p5; p1 = p1->next; } while(p2!=NULL)//p2较长 { sum = p2->val + carry; if(sum>9) { sum%=10; carry = 1; } else { carry = 0; } struct ListNode *p6 = (struct ListNode*)malloc(sizeof(struct ListNode)); p6->val = sum; p6->next = NULL; p3->next = p6; p3 = p6; p2 = p2->next; } if(carry == 1)//完成两条链表的值合并，但是最大值位发生进位的处理 { sum = carry; struct ListNode *p7 = (struct ListNode*)malloc(sizeof(struct ListNode)); p7->val = sum; p7->next = NULL; p3->next = p7; } return l3->next; }