两数相加题解

题目来源：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
 

思路：

模拟求解

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2 进位值为 carry，则它们的和为n1+n2+carry；

其中，答案链表处相应位置的数字为(n1+n2+carry)mod10，而新的进位值为(n1+n2+carry)/10
​

如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 00 。

此外，如果链表遍历结束后，有 carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry

python解法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = point=ListNode(0)		#当前结点初始化为返回列表的哑结点
        carry = 0   #进位初始化为0
#遍历l1,l2直到他们的尾端
        while(l1 or l2):
            new_point=ListNode(0)
            if not l1:				#若达到l1的末尾，只计算l2
                sum_=l2.val + carry
                new_point.val = sum_ % 10
                carry = sum_ //10
                l2 = l2.next

            elif not l2:		#若达到l2的末尾，只计算l1
                sum_ = l1.val + carry
                new_point.val = sum_ % 10
                carry = sum_ //10
                l1 = l1.next
            
            else:
                sum_ = l1.val + l2.val + carry		#sum = x + y +carry
                new_point.val = sum_ % 10		#创建一个数值为sum_%10的新结点，并将其设置为当前节点的下一个结点，然后将当前结点前进到下一个结点
                carry = sum_ // 10
                l1 = l1.next		#将l1,l2前进到下一个结点
                l2 = l2.next
            point.next = new_point
            point = point.next
        if carry:				#检查carry是否为1，如果为1，则向返回列表追加一个含有数字为1的新节点
            new_point = ListNode(1)
            point.next = new_point
        return head.next

c语言代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *head = NULL,*tail = NULL;
    int carry = 0;//进位
    while(l1||l2)//l1和l2有一个不为0
    {
        int n1 = l1 ? l1->val:0;      //链表为空的地方置0
        int n2 = l2 ? l2->val:0;
        int sum = n1 + n2 +carry;
        if(!head)//head为空 新建链表 head and tail指向第一个结点
        {
            head = tail = malloc(sizeof(struct ListNode));
            tail->val = sum % 10;
            tail->next = NULL;
        }
        else{//将后面相加得到的值加入新的链表
           tail->next = malloc(sizeof(struct ListNode));
            tail->next->val = sum % 10;
            tail = tail->next;
            tail->next = NULL;
        }
        carry = sum /10;
        if(l1)
        {
            l1 =l1->next;
        }
        if(l2)
        {
            l2 = l2->next;
        }
    }
        if(carry>0)
        {
            tail->next = malloc(sizeof(struct ListNode));
            tail->next->val = carry;
            tail->next->next=NULL;
        }
        return head;