原创

LeetCode-2.两数相加


2、两数相加

[TOC]

题目描述

  • 给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储一位数字。

  • 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

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

  • 示例:

    输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出:7 -> 0 -> 8
    原因:342 + 465 = 807
    

解题思路

低位进位法(常规做法)
  • 分析:

    • 对应位置的数相加,满10进位,取10模赋值
    • 注意:
      • 位数不同时需使用0进行操作
      • 位数相同最高位有进位需新增节点
  • 代码实现

    /**
     * 常规做法
     *
     * @param l1 1
     * @param l2 2
     * @return: questions.ListNode
     **/
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //初始化头结点
        ListNode initHeadNode = new ListNode(0);
        //初始化进位数
        int carry = 0;
        ListNode p1 = l1, p2 = l2, temp = initHeadNode;
        while (p1 != null || p2 != null) {
            int val1 = p1 == null ? 0 : p1.val;
            int val2 = p2 == null ? 0 : p2.val;
            int result = val1 + val2 + carry;
            //如果和大于或等于10则代表有进位
            if (result >= 10) {
                carry = 1;
                result = result - 10;
            } else {
                carry = 0;
            }
            //新建节点
            temp.next = new ListNode(result);
            temp = temp.next;
            p1 = p1.next;
            p2 = p2.next;
        }
        //如果最后结果仍有进位,则需要再次新增节点
        if (carry > 0) {
            temp.next = new ListNode(1);
        }
        //返回实际头结点
        return initHeadNode.next;
    }
    
  • 复杂度分析:假设 m 和 n分别表示 l1 和 l2 的长度

    • 时间复杂度:
      • O(max(m,n))
    • 空间复杂度:
      • O(max(m,n))

扩展

如果将题目中的逆序修改为顺序,则如何解?

思路

  • 有的人可能考虑使用递归或栈来做,但是这样可能导致栈内存溢出,因为链表长度不可控制。
  • 可以考虑先将链表倒置,调用上述方法后再倒置回来。
  • 时间复杂度:O(max(m,n)+m+n)=O(max(m,n))
  • 空间复杂度:O(max(m,n))
  • 缺点:会改变用户的输入(可以改进,倒置链表时复制一份链表的副本,但是会增加空间复杂度)

代码实现

/**
     * 扩展题解法
     *
     * @param l1 1
     * @param l2 2
     * @return: questions.ListNode
     * @auther: xianzilei
     * @date: 2019/10/7 8:05
     **/
public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
    //倒置链表l1和l2
    ListNode temp1 = reverse(l1);
    ListNode temp2 = reverse(l2);
    //求和
    ListNode temp3 = addTwoNumbers1(temp1, temp2);
    //倒置结果
    return reverse(temp3);
}

//反转链表
private static ListNode reverse(ListNode l) {

    if (l == null || l.next == null) {
        return l;
    }
    ListNode prev = l;
    ListNode cur = l.next;
    l.next = null;
    ListNode next = null;
    while (cur != null) {
        next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}
Java
算法
  • 作者:贤子磊(联系作者)
  • 发表时间:2019-11-28 20:45
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 公众号转载:请在文末添加作者公众号二维码
  • 评论