2.两数相加Java

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入输出样式

示例1：

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

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

本题来自LeetCode：https://leetcode-cn.com/problems/add-two-numbers/

思路

依次遍历双链表把对应的val相加，这里要注意进位carry。每次相加为(val1+val2+carry) % 10，而进位carry = (val1+val2+carry) / 10。当某一链表遍历到尾部后将还未遍历完的链表过去，但是要注意carry对其产生的影响。最后完毕后，还要检测carry是否为1，如果唯一说明还要新增一个val = 1的节点。

算法分析

时间复杂度O(max(m, n)），空间复杂度为O(1)

求解函数

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dum = new ListNode();
        //dum为p2的前一个指针
        dum.next = l2;
        ListNode p1 = l1, p2 = l2, p = dum;
        //进位标志
        int carry = 0;
        //将l1链表的节点值加到l2中
        while (p1 != null && p2 != null) {
            int temp = (p2.val + p1.val + carry) / 10;
            p2.val = (p2.val + p1.val + carry) % 10;
            carry = temp;
            p1 = p1.next;
            p2 = p2.next;
            p = p.next;
        }
        //都遍历完毕，则根据carry为判断是否还需要新建val=1的节点
        if (p1 == null && p2 == null) {
            if (carry == 1) {
                p.next = new ListNode(1);
            }
            return l2;
        } else if (p1 == null && p2 != null) {
        //l2还未遍历完，根据carry更新对剩余节点的影响
            p.next = p2;
            while (p2 != null) {
                int temp = (carry + p2.val) / 10;
                p2.val = (p2.val + carry) % 10;
                carry = temp;
                p2 = p2.next;
                p = p.next;
            }
            if (carry == 1) {
                p.next = new ListNode(1);
            }
            return l2;
        } else {
         //l1还未遍历完，根据carry更新对剩余节点的影响
            p.next = p1;
            while (p1 != null) {
                int temp = (carry + p1.val) / 10;
                p1.val = (p1.val + carry) % 10;
                carry = temp;
                p1 = p1.next;
                p = p.next;
            }
            if (carry == 1) {
                p.next = new ListNode(1);
            }
            return l2;
        }
    }
}