美文网首页
LeeCode02-两数相加(多解法)

LeeCode02-两数相加(多解法)

作者: 键盘上的码农 | 来源:发表于2021-08-13 13:37 被阅读0次

首先看题目:
给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表。

示例 1:


addtwonumber1.jpeg
输入: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]

链表节点:

@Setter
@Getter
public class ListNode {

    private int val;

    private ListNode next;

    public ListNode() {}

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

解法一:初等数学
两个链表中同一位置的数字可以直接相加,如果两个链表的长度不同,则可以认为短链表不足的节点都是0.

我们同时遍历两个链表,逐位计算它们的和,并与当前位置的进位值相加。j链表1的节点值是n1,链表2的节点值是n2,进位值为carray。当前节点的值是(n1+n2+carry)%10,新的进位值为(n1+n2+carry)/10。

此外,如果链表遍历结束后依然有进位制,即carry>0,那还需要在答案链表的后面附加一个节点,节点的值为carry。

直接贴代码:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//    时间复杂度:O(max(m,n)),其中 mm 和 nn 分别为两个链表的长度。我们要遍历两个链表的全部位置,而处理每个位置只需要 O(1)的时间。
//    空间复杂度:O(1)。
    if (l1 == null && l2 == null) {
        return null;
    }
    // 头部的节点
    ListNode head = null;
    // 尾部的节点
    ListNode tail = null;
    // 进位值
    int carryVal = 0;
    while (l1 != null || l2 != null) {
        int v1 = l1 != null ? l1.val : 0;
        int v2 = l2 != null ? l2.val : 0;
        // 两节点值+进位值
        int sum = v1 + v2 + carryVal;
        // 相加后节点的的值是sum对10取余
        int tailVal = sum % 10;
        // 当前节点计算后的进位值
        carryVal = sum / 10;
        if (head == null) {
            head = tail = new ListNode(tailVal);
        } else {
            tail.next = new ListNode(tailVal);
            tail = tail.next;
        }
        if (l1 != null) {
            l1 = l1.next;
        }
        if (l2 != null) {
            l2 = l2.next;
        }
    }
    // l1 和 l2 节点全部相加完后还有进位值,则构建最后一个节点,值为carryVal
    if (carryVal > 0) {
        tail.next = new ListNode(carryVal);
    }
    return head;
}

解法二:改进版
这是在解法一上的修改版,区别在于,如果两个链表的长度不等,则只根据长链表进行计算,如果在某一个节点进位数为0,则不需要再遍历长链表,直接指向长链表剩余的节点就可以了。

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null && l2 == null) {
        return null;
    }
    // 头部的节点
    ListNode head = null;
    // 尾部的节点
    ListNode tail = null;
    head = tail =  new ListNode(0);
    // 进位值
    int carryVal = 0;
    while (l1 != null && l2 != null) {
        // 两节点值+进位值
        int sum = l1.val + l2.val + carryVal;
        // 相加后节点的的值是sum对10取余
        int tailVal = sum % 10;
        // 当前节点计算后的进位值
        carryVal = sum / 10;
        tail.next = new ListNode(tailVal);
        tail = tail.next;
        l1 = l1.next;
        l2 = l2.next;
    }
    // 基于长链表继续计算
    ListNode lNode = l1 != null ? l1 : l2 != null ? l2 : null;
    while (lNode != null) {
        if (carryVal > 0) {
            int sum = lNode.val + carryVal;
            int tailVal = sum % 10;
            carryVal = sum / 10;
            tail.next = new ListNode(tailVal);
            tail = tail.next;
            lNode = lNode.next;
        } else {
            tail.next = lNode;
            break;
        }
    }
    // l1 和 l2 节点全部相加完后还有进位值,则构建最后一个节点,值为carryVal
    if (carryVal > 0) {
        tail.next = new ListNode(carryVal);
    }
    return head.next;
}

小提示:也有一些解法是不新建链表,而是基于某一个链表进行操作。但是几乎所有解法用到的数学思路都差不多。

相关文章

  • LeeCode02-两数相加(多解法)

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

  • LeetCode-加一

    题目链接 => 戳这里 解法:这道题其实有点像两数相加那道题

  • 算法(leetode,附思维导图 + 全部解法)300题之(2)

    标题:算法(leetode,附思维导图 + 全部解法)300题之(2)两数相加 导读: 项目&作者 1 GitHu...

  • 2018-11-26 两数相加

    题目: 2. 两数相加 解法: 因为列表是逆序的, 所以恰好就从个位开始. 所以我们只需要对应的数位相加.然后再判...

  • 算法:不使用乘除求数的平方

    算法 不使用乘法和除法,求一个数的平方 解法 1: a^2 = a * a, 相当于a个a相加 解法 2: 1^2...

  • 两数相加

    题目 You are given two non-empty linked lists representing ...

  • 两数相加

    给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表...

  • 两数相加

    两数相加 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一...

  • 两数相加

    两数相加: 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回...

  • 两数相加

    题目 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新...

网友评论

      本文标题:LeeCode02-两数相加(多解法)

      本文链接:https://www.haomeiwen.com/subject/euidbltx.html