Leetcode 每日一题 day2 2022.1.2

题目

两数相加
链接:https://leetcode-cn.com/problems/add-two-numbers/

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
Leetcode 每日一题 day2 2022.1.2

思路

因为给的链表是倒序的,也就是低位再前,高位在后,而加法运算刚好是从低位开始相加,所以刚好可以从头遍历链表,将两个链表对应的值相加,用一个变量carry作为进位位。
将两个链表共有的部分处理完了之后,再处理剩余的一个链表,链表中的值处理完之后,再处理最后一个进位位。

代码(c++版本)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode *p1 = l1;
        ListNode *p2 = l2;
        int carry=0;
        

    
        ListNode *result = new ListNode(-1);
        ListNode *head = result;
        while(p1!=NULL&&p2!=NULL)
        {
            int i=(p1->val+p2->val+carry);
           
            result->next = new ListNode(i%10);
   
            if(i>=10) carry=1;
            else carry=0;
            p1=p1->next;
            p2=p2->next;
            result=result->next;
        }
        while(p1!=NULL)
        {   
            int i = carry+p1->val;
            cout<<i<<" ";
            result->next = new ListNode(i%10);
            if(i>=10) carry=1;
            else carry=0;
            p1=p1->next;
            result = result->next;
        }
          while(p2!=NULL)
        {   
            int i = carry+p2->val;
            result->next = new ListNode(i%10);
            if(i>=10) carry=1;
            else carry=0;
            p2=p2->next;
            result = result->next;
        }

        if(carry!=0){      //处理最后一个进位位,主要是针对示例3的情况
            result->next = new ListNode(carry);  
        }
        return head->next;

    }
};

代码(golang版本)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    
    carry :=0
    p1 := l1
    p2 := l2
    result := &ListNode{Val:-1,Next:nil}
    head := result
    for p1!=nil && p2!=nil{
        var i int
        i=(p1.Val+p2.Val+carry)
        result.Next = &ListNode{Val:i%10,Next:nil}
        if i>=10 {
            carry=1
        }else{
            carry=0
        } 
        p1 = p1.Next
        p2 = p2.Next
        result = result.Next

    }
    for p1!=nil{
        var i int
        i=(p1.Val+carry)
        result.Next = &ListNode{Val:i%10,Next:nil}
        if i>=10 {
            carry=1
        }else{
            carry=0
        } 
        p1 = p1.Next
        result = result.Next
    }
     for p2!=nil{
        var i int
        i=(p2.Val+carry)
        result.Next = &ListNode{Val:i%10,Next:nil}
        if i>=10 {
            carry=1
        }else{
            carry=0
        } 
        p2 = p2.Next
        result = result.Next
    }

    if carry>0{
        result.Next = &ListNode{Val:carry,Next:nil}
    }
    return head.Next

}
上一篇:Java基础day2


下一篇:2022-1-2队列/栈day2