0001-两数之和

简介

2. 两数相加

难度: 中等

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

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

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

示例 1：

image 

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

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

环境

** GO语言

正文

1. 分析

审题:

    1. 两个非空的链表，每个链表节点存储非负的整数（包含零），并链表值是逆序排列。并且每个节点只能存储 一位 数字。
    1. 两个链表存储的数相加返回一个表示和的链表。
    1. 除非链表表示的数值为0，否则链表开始不能为零
    1. 其实这里链表表示的就是一个非负的整数。二不同节点表示数的位数。而两个链表相加就是两个非负的整数相加（[2,4,3]+[5,6,4] == 342+465 == 807 == [7,0,8]）（[9,9,9,9,9,9,9] + [9,9,9,9] == 9999999 + 9999 == 10009998 == [8,9,9,9,0,0,0,1] ）

思路:

    1. 需要一个循环获取节点值,两节点数值相加取余就是个位数，相加值除10就是进位数

注:

  • 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。 一个排列中所有逆序的总数叫做这个排列的逆序数。

2. 源码

  • Golang语言
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    header := ListNode{0, nil}
    next1, next2, sumNext := l1, l2, &header
    up, sum := 0, 0
    doSum := true
    for doSum {
        if next1 == nil && next2 != nil {
            sum = sumNext.Val + next2.Val
            next2 = next2.Next
        } else if next2 == nil && next1 != nil {
            sum = sumNext.Val + next1.Val
            next1 = next1.Next
        } else {
            sum = sumNext.Val + next1.Val + next2.Val
            next2 = next2.Next
            next1 = next1.Next
        }
        up = sum / 10
        if up > 0 {
            sumNext.Val = sum - 10
        } else {
            sumNext.Val = sum
        }
        doSum = next1 != nil || next2 != nil
        if doSum || up > 0 {
            sumNext.Next = &ListNode{up, nil}
            sumNext = sumNext.Next
        }
    }
    return &header
}
  • Python语言
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            if target-nums[i] in nums[i+1:]:
                return [i, nums.index(target-nums[i], i+1)]

结束