两数相加

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

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

你可以假设除了数字 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