两个数字相加表示为链表☆☆☆

作者 : IT 大叔 本文共1032个字,预计阅读时间需要3分钟 发布时间: 2020-10-13

主题链表

问题:

您将获得两个表示两个非负整数的非空链表。这些数字以相反的顺序存储,并且它们的每个节点都包含一个数字。将两个数字相加,并将其作为链表返回。

您可能会假定两个数字除了数字0本身以外都不包含任何前导零。

例:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解:

您可以用手动添加两个数字的方式来添加使用LinkedLists表示的两个数字。

遍历链表,添加它们的对应元素,保持进位与您手工添加数字时的方式相同,将前一个加法后的结余添加到当前总和中,依此类推。

这个问题中最棘手的部分之一就是进位号的问题-如果每对节点加到的数字小于10,那么就不必担心将数字“携带”到下一个节点。但是,将数字4和6相加会产生进位。

如果一个列表比另一个列表长,我们仍然希望将更长列表的节点添加到解决方案中,因此,只要节点不为空,我们就必须确保继续进行检查。这意味着,只要列表1不是null或列表2不是,while循环就应该继续进行null

实现方式:

JAVA

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    ListNode result = head;
    int carry = 0;

    while (l1 != null || l2 != null || carry > 0) {
        int resVal = (l1 != null? l1.val : 0) + (l2 != null? l2.val : 0) + carry;
        result.next = new ListNode(resVal % 10);
        carry = resVal / 10;
        l1 = (l1 == null ? l1 : l1.next);
        l2 = (l2 == null ? l2 : l2.next);
        result = result.next;
    }

    return head.next;
}

Y

class Solution:
# @return a ListNode
def addTwoNumbers(self, l1, l2):
    carry = 0
    root = n = ListNode(0)
    while l1 or l2 or carry:
        v1 = v2 = 0
        if l1:
            v1 = l1.val
            l1 = l1.next
        if l2:
            v2 = l2.val
            l2 = l2.next
        carry, val = divmod(v1+v2+carry, 10)
        n.next = ListNode(val)
        n = n.next
    return root.next
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 两个数字相加表示为链表☆☆☆

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论