leecode-第二题-两数相加

题目描述

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

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

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

示例：

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

代码

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int flag = 0, x1 = 0, x2 = 0,a,b;struct ListNode *p1=l1,*p2=l2,*b1 = l1, *b2 = l2,*f1 = l1,*f2 = l2, *p3;if(l1==NULL&&l2==NULL)return NULL;while(p1!=NULL&&p2!=NULL){
      // 判断两个链表的长度p1 = p1->next;p2 = p2->next;if(p1!=NULL){
    x1 ++;}if(p2!=NULL){
    x2 ++;} }    while(l1!=NULL && l2!= NULL){
      // 当其中一个链表已经到达最高位，则进入下一步a = l1->val;b = l2->val;if(x1 >= x2)if(flag == 1){
    l1->val = (a + b + 1) % 10;a += 1; // 此处注意}elsel1->val = (a + b) % 10;            elseif(flag == 1){
    l2->val = (a + b + 1) % 10;b += 1; // 此处注意}elsel2->val = (a + b) % 10;      if(a + b >= 10)flag = 1;elseflag = 0;       l1 = l1->next;l2 = l2->next;       } CD:if(flag == 1){
      // 一个链表到达最高位后的计算if(x1>=x2)if(l1 == NULL){
                  p3 = (struct ListNode *)malloc(sizeof(struct ListNode));p3->val = 1;p3->next =NULL;while(f1->next != NULL)f1 = f1->next;f1->next = p3;f1 = p3;}else{
    l1->val += 1;if(l1->val >= 10){
    l1->val = l1->val%10;                    l1 = l1->next;goto CD;}}elseif(l2 == NULL){
    p3 = (struct ListNode *)malloc(sizeof(struct ListNode));p3->val = 1;p3->next =NULL;while(f2->next != NULL)f2 = f2->next;f2->next = p3;f2 = p3;}else{
    l2->val += 1;               if(l2->val >= 10){
    l2->val = l2->val%10;                 l2 = l2->next;goto CD;}}if(x1 >= x2)return b1;elsereturn b2;
}

执行用时 : 44 ms, 在Add Two Numbers的C提交中击败了67.49% 的用户
内存消耗 : 8.2 MB, 在Add Two Numbers的C提交中击败了99.84% 的用户

代码描述

两个链表数字相加，其中一个链表到达最高位后，进行其他高位的运算。如果最高位还需要进位，用动态分配给进位的数，此时最高位只可能是1。代码用时较长，可能是goto语句用时长。

参考代码

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int num, temp = 0;struct ListNode * outputNode = (struct ListNode *)malloc(sizeof(struct ListNode));outputNode -> next = NULL;struct ListNode * tail = outputNode;while(l1 || l2){
    num = 0;if(l1 != NULL){
    num += l1->val;l1 = l1->next;}if(l2 != NULL){
    num += l2->val;l2 = l2->next;}num += temp;temp = 0;if(num >= 10){
    num %= 10;temp = 1;}tail -> val = num;if(l1 || l2){
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode -> next = NULL;tail -> next = newNode;tail = tail -> next;}}if(temp){
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode -> next = NULL;tail -> next = newNode;tail = tail -> next;tail -> val = temp;}return outputNode;
}

改进代码(c语言)

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *p1=l1, *p2 = l2, *p3, *p4;int k=0,temp = 0, a, b;while(p1 != NULL&&p2 != NULL){
    p1 = p1->next;p2 = p2->next;    }if(p1 == NULL){
    p4 = l2; k=1;}elsep4 = l1;p1 = l1;p2 =l2;while(p4 != NULL){
    if(p1 != NULL){
    a = p1->val;p1 = p1->next;}elsea = 0;if(p2 != NULL){
    b = p2->val;p2 = p2->next;}else b = 0;p4->val = (a + b + temp) % 10;p3 = p4;p4 = p4->next;if(a + b + temp>= 10)temp = 1;else temp = 0;      }if(temp){
    p4 = (struct ListNode*)malloc(sizeof(struct ListNode));p4->val = 1;p4->next = NULL;p3 ->next = p4;}if(k==1)return l2;elsereturn l1;
}

执行用时 : 24 ms, 在Add Two Numbers的C提交中击败了96.84% 的用户
内存消耗 : 8.5 MB, 在Add Two Numbers的C提交中击败了97.39% 的用户

解答思路(Java)

标准答案

java

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;
}

执行用时 : 10 ms, 在Add Two Numbers的Java提交中击败了91.05% 的用户
内存消耗 : 45.2 MB, 在Add Two Numbers的Java提交中击败了80.87% 的用户