Leetcode第二题，用链表实现两个非负整数求和Leetcode第二题，用链表实现两个非负整数求和

104 阅读 0 评论 69 点赞

我是靠谱客的博主体贴小海豚，最近开发中收集的这篇文章主要介绍Leetcode第二题，用链表实现两个非负整数求和Leetcode第二题，用链表实现两个非负整数求和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Leetcode第二题，用链表实现两个非负整数求和

问题描述：给定两个存放非负整数的链表（不带头结点）,逆序存放并且每一个节点只存放一个数字，现要求对这两个数字求和并以链表的形式返回。
例子：
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

思路：
-1 由于这两个非负整数是逆序存放，而且求和结果也需要逆序存放到一个链表中，故只需要对链表中逆序存放的的两个数从左到右求和（对称求和），然后把结果顺序存放到结果链中即可，即：
链表1 2 4 3
+
链表2 5 6 4
=
链表3 7 0 8
- 2 那么如何实现求和运算呢，我们根据加法原理知道，两个数字求和，即是从个位开始，把相应位置上的数字求和然后加上上一位数字求和的进数（除以10的整数部分），然后把得到的结果除以10的余数作为该位的求和结果，除以10的整数部分作为进数加到下一位去，重复此过程直到没有数字可以使用为止。
根据以上思路我们就可以进行加法程序设计了。由于数字的位数可能不同，这里我们分两种情况考虑：
(1)链表1和链表2存储的整数的位数相同。对两个链表的对应位置进行循环求和（使用上面的思路），直到节点为空没有数字可以求和。然后对最高位的进数进行判断，如果进数为0，则返回结果链表，否则用一个新的节点去存储这个进数并继续添加到结果链表中去，然后返回结果。
(2)链表1中的整数比链表2中的整数位数不等，不妨设链表1中整数的位数比链表2多。对于这种情况，我们只需要考虑访问完链表2时的操作。当访问完链表2时，这时我们链表1中还有数字没有访问完。这时候我们就用0去表示链表2相应位置上的元素，并继续进行加法求和过程，最后直到链表1中所有元素访问完毕。其他过程均同(1)

C语言代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *l3,*p,*node1,*node2,*tmp;
    //l3用于存储结果，p用来存放对应位置上的加法结果，node1和node2用来遍历接受到的两个链表，tmp指针用来顺序生成结果链表
    int a,tmp1;//a用来存放进数，tmp1用来存放对应位置的求和加上进数的结果
    l3 = tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
    l3->next = NULL;
    node1 = l1;
    node2 = l2;
    a = 0;
    while((node1 != NULL)||(node2 != NULL)){
        p = (struct ListNode*)malloc(sizeof(struct ListNode));
        if((node1 != NULL)&&(node2 != NULL))
            tmp1 = node1->val+node2->val+a;
        else if(node1 == NULL) //链表1短的情况
            tmp1 = node2->val+a;
        else //链表2短的情况
            tmp1 = node1->val+a;
        p->val = tmp1%10;//存放当前位置求和结果
        p->next = tmp->next;
        tmp->next = p;
        tmp = p;
        a = tmp1/10;//生成新的进数
        if((node1 != NULL)&&(node2 != NULL)){
            node1 = node1->next;
            node2 = node2->next;
        }
        else if(node1 == NULL)
            node2 = node2->next;
        else
            node1 = node1->next;
    }
    if(a != 0){//判断最高位的进数是不是为0
        p = (struct ListNode*)malloc(sizeof(struct ListNode));
        p->val = a;
        p->next = tmp->next;
        tmp->next = p;
    }
    return (l3->next);//我们的生成的链表是带头结点的，我试验了一下题目要求返回的是不带头结点的，所以返回去掉头结点的链表
}