Loading...
墨滴

编程熊

2021/07/01  阅读:49  主题:橙心

【LeetCode每日一题 Day 2】 2. 两数相加

大家好,我是编程熊,今天是LeetCode每日一题的第二天,一起学习的是LeetCode第二题《两数相加》。

题意

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

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

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

示例

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

题解

因为链表是逆序的,所以两个链表可以从头开始逐位相加,但两个链表可能不一样长,对于短的链表可以高位补 0 。 需要注意的是,遍历完两个链表后,最高位需要进位而额外增加一位。

时间复杂度: n 为两个链表中较长的长度。

空间复杂度:

知识点总结: 链表

C++代码

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode* head = new ListNode();
        ListNode* currentPos = head;
        int v = 0;
        while(l1 || l2 || v) {
            int v1 = l1 ? l1->val : 0, v2 = l2 ? l2->val : 0;
            int res = (v + v1 + v2) / 10;
            v = (v1 + v2 + v) % 10;
            currentPos->val = v;
            v = res;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
            if (l1 || l2 || v) {
                currentPos->next = new ListNode();
                currentPos = currentPos->next;
            }
        }
        return head;
    }
};

Java代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode currentPos = head;
        int v = 0;
        while (l1 != null || l2 != null || v != 0) {
            int v1 = l1 != null ? l1.val : 0;
            int v2 = l2 != null ? l2.val : 0;
            int res = (v + v1 + v2) / 10;
            v = (v + v1 + v2) % 10;
            currentPos.val = v;
            v = res;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
            if (l1 != null || l2 != null || v != 0) {
                currentPos.next = new ListNode();
                currentPos = currentPos.next;
            }
        }
        return head;
    }
}

题目链接: https://leetcode-cn.com/problems/add-two-numbers/

我是编程熊,致力于让大家都成为更好的人,欢迎 『关注』、『点赞』、『转发』支持~

编程熊

2021/07/01  阅读:49  主题:橙心

作者介绍

编程熊

公众号: 编程熊