[LeetCode] 445. Add Two Numbers II

alexnevsky 发布于2019-08-16 13:56 / 965人阅读

Problem

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

Solution

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        //add
        ListNode dummy = new ListNode(0), l3 = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            l3.next = new ListNode(sum%10);
            l3 = l3.next;
            carry = sum/10;
        }
        if (carry != 0) l3.next = new ListNode(carry);
        return reverse(dummy.next);
    }
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

云服务器 GPU云服务器 Numbers 电信445 LeetCode 网易云服务器错误445

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72591.html

leetcode445. Add Two Numbers II

摘要：题目要求对以链表形式的两个整数进行累加计算。思路一链表转置链表形式跟非链表形式的最大区别在于我们无法根据下标来访问对应下标的元素。因此这里通过先将链表转置，再从左往右对每一位求和来进行累加。通过栈可以实现先进后出，即读取顺序的转置。题目要求 You are given two non-empty linked lists representing two non-negative i...

DoINsiSt 2019-08-16 17:30 评论0 收藏0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

摘要：公众号爱写给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值和，其中必须小于。示例输入输出解释与之和等于目标数。公众号：爱写bug（ID：icodebugs）给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。...

张春雷 2019-08-16 18:29 评论0 收藏0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

摘要：公众号爱写给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值和，其中必须小于。示例输入输出解释与之和等于目标数。公众号：爱写bug（ID：icodebugs）给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。...

Me_Kun 2019-07-31 11:26 评论0 收藏0
leetcode 167 Two Sum II - Input array is sorted

摘要：同时题目假设每组输入恰好只有一个答案，并且不能重复使用同一元素。理解这道题是可以用两层循环蛮力解决的，但是效率太低了。如果这两个元素和大于目标数组，指针左移如果小于，指针右移。如果等于，则返回这两个元素的位置记得用数组的数值加一解法题目详情 Given an array of integers that is already sorted in ascending order, fi...

Keagan 2019-08-15 13:44 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0