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

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

题意

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

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

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

示例

输入：l1 = [2,4,3], l2 = [5,6,4]

输出：[7,0,8]

解释：342 + 465 = 807.

题解

因为链表是逆序的，所以两个链表可以从头开始逐位相加，但两个链表可能不一样长，对于短的链表可以高位补 0 。

需要注意的是，遍历完两个链表后，最高位需要进位而额外增加一位。

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

空间复杂度: O(1)

知识点总结: 链表

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/

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

巴特西

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

题意

题解

C++代码

Java代码

最新文章

热门文章