两数相加

题目

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

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

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

 

示例 1:

输入: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
  • 题目数据保证列表表示的数字不含前导零

解题方法一

/**
     * 先获取两个链表的长度len1、len2,比较出较长longList和较短shortList链表并用指针记录curL、curS,
     * 然后分三种情况:
     * 1)当两条链表都有元素时 curS != null
     * - 将两条链表对应节点元素值与进位值相加,得到的此值%10得出此位上的值并直接赋给curL.val
     * - 将相加结果/10 求得进位值
     * - last = curL; last作为记录最后一个节点,以便最后需要进位时直接再其后增加
     * - curL、curS向后移动;
     * 2)当较短链表没有元素时 curL != null
     * - 将curL对应节点元素值与进位值相加,得到的此值%10得出此位上的值并直接赋给curL.val
     * - 将相加结果/10 求得进位值
     * - last = curL;
     * - curL向后移动;
     * 3)当两条链表都没元素时
     * - 判断最后进位是否为0
     * - carry != 0 表示需要进位 last.next = new ListNode(1);
     * <p>
     * 最后返回longList
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 获取两个链表长度
        int len1 = getLength(l1);
        int len2 = getLength(l2);
        // 创建较长链表和较短链表的指针
        ListNode longList = len1 >= len2 ? l1 : l2;
        ListNode shortList = longList == l1 ? l2 : l1;
        ListNode curL = longList;
        ListNode curS = shortList;
        // last作为记录最后一个节点,以便最后需要进位时直接再其后增加
        ListNode last = curL;
        int carry = 0;  //进位标志
        int curNum = 0;
        //当短链表不为空时,两条链表同时都有值
        while (curS != null) {
            curNum = curL.val + curS.val + carry;
            curL.val = (curNum % 10);
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
            curS = curS.next;
        }
        // 当跳出上一个循环时,表明短链表为空
        while (curL != null) {
            curNum = curL.val + carry;
            curL.val = (curNum % 10);
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
        }
        // 当跳出上一个循环时,表明两条链表全部节点遍历结束
        // 如果有进位 则在最后新增节点1
        if (carry != 0) {
            last.next = new ListNode(1);
        }
        return longList;
    }
    // 求链表长度
    private static int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

 

解题方法二

/**
     * 总体分为两步: 按位相加  and  进位
     * 这个方法代码比较容易理解
     * 需要注意特殊情况的处理:
     * 当l2.len > l1.len
     * 当最后需要进位时
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2){
        ListNode head1 = l1;
        ListNode head2 = l2;
        // 按位相加
        while (head1 != null){
            if (head2 != null){
                head1.val +=  head2.val;
                head2 = head2.next;
            }
            if (head1.next == null && head2 != null){
                head1.next = head2;
                break;
            }
            head1 = head1.next;
        }
        // 进位
        merge(l1);
        return l1;
    }
    // 进位
    public void merge(ListNode head1) {
        while (head1 != null){
            if (head1.val >= 10){
                head1.val = head1.val % 10;
                if (head1.next == null){
                    head1.next = new ListNode(0);
                }
                head1.next.val += 1;
            }
            head1 = head1.next;
        }
    }

 

微信关注

WeChat

阅读剩余
THE END