两数相加

一、问题描述

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

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

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

示例：

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

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

二、解决方案

题目要求的返回结果为链表的头节点，需要遍历两个链表，在遍历两个链表的过程中，计算结果链表中各个位置的值。

链表中每个位置的取值为 0 到 9，所以每个位置两个值相加范围在 0 到 18，当计算结果大于等于 10 时，需要进位。当前位置保留的值为和除以 10 的余数，下一个节点的初始值为 1。

三、Java 代码实现

ListNode 节点：

@Data
@NoArgsConstructor
public class ListNode {

    int val;

    ListNode next;

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

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

    @Override
    public String toString() {
        return val + "" + (next == null ? "" : next);
    }
}

实现：

public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
    ListNode resultNode = new ListNode();
    ListNode tempNode = resultNode;
    
    while (l1 != null || l2 != null) {
        // 判断两个输入链表中当前节点的值
        int num = l1 == null ? 0 : l1.val;
        int num2 = l2 == null ? 0 : l2.val;
    
        int sum = num + num2 + tempNode.val;
        // 计算结果链表中当前节点的值
        tempNode.val = sum % 10;
    
        if (l1 != null) {
            l1 = l1.next;
        }
        if (l2 != null) {
            l2 = l2.next;
        }
        if (l1 != null || l2 != null || sum >= 10) {
            // 结果链表当前节点的 next 新建并赋值，赋值为当前节点计算的商
            tempNode.next = new ListNode(sum / 10);
            tempNode = tempNode.next;
        }
    }
    return resultNode;
}

递归实现：

public ListNode addTwoNumbersRecursion(ListNode l1, ListNode l2) {

    // 如果两个链表的节点存在 null 的话，则不需要相加了，直接返回另一个链表的节点
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }

    // 两个链表节点的和
    int sum = l1.val + l2.val;
    // 当前节点为两个链表节点和取余
    ListNode resultNode = new ListNode(sum % 10);
    // 下一个节点由两个链表节点的下一个节点来计算
    resultNode.next = addTwoNumbersRecursion(l1.next, l2.next);
    // 如果和大于 10，需要将十位上的数值进到下一位
    // 由因为本题目的前提条件是入参链表节点的 值 >= 0 && 值 <= 9，所以和最大为 18 最小为 0，所以只用判断是否大于 10 即可
    if (sum >= 10) {
        // 和大于 10，则需要进位，需要在当前节点的下一个节点上再加 1，所以需要重新获取 resultNode.next
        // 入参中，第一个参数为之前的计算结果，第二个参数为需要进位的 1
        resultNode.next = addTwoNumbersRecursion(resultNode.next, new ListNode(1));
    }
    return resultNode;
}

Junit 5 测试代码：

@Slf4j
class SolutionTest {

    @Data
    @Accessors(chain = true)
    @NoArgsConstructor
    @AllArgsConstructor
    private static class InputOutput {

        private ListNode inputListNode;

        private ListNode inputListNode2;

        private ListNode resultListNode;
    }

    private final Solution solution = new Solution();

    private final List<InputOutput> inputOutputList = List.of(
            // 342 + 465 = 807
            new InputOutput(
                    initListNodeByString(342),
                    initListNodeByString(465),
                    initListNodeByString(807)
            ),
            // 0 + 0 = 0
            new InputOutput(
                    initListNodeByString(0),
                    initListNodeByString(0),
                    initListNodeByString(0)
            ),
            // 9_999_999 + 9999 = 10_009_998
            new InputOutput(
                    initListNodeByString(9_999_999),
                    initListNodeByString(9_999),
                    initListNodeByString(10_009_998)
            )
    );

    /**
     * 入参为 342，则转换为链表，为 2 -> 4 -> 3
     *
     * @param num     数字
     */
    private ListNode initListNodeByString (int num) {
        String numString = String.valueOf(num);
        ListNode resultListNode = new ListNode();
        ListNode tempNode = resultListNode;
        for (int i = numString.length() - 1; i >= 0; i--) {
            char c = numString.charAt(i);
            tempNode.val = Integer.parseInt(String.valueOf(c));
            if (i > 0) {
                tempNode = tempNode.next = new ListNode();
            }
        }
        return resultListNode;
    }

    @Test
    void initListNodeByString() {
        Assertions.assertEquals("243", initListNodeByString(342).toString());  
        Assertions.assertEquals("0", initListNodeByString(0).toString());  
        Assertions.assertEquals("01", initListNodeByString(10).toString());
    }

    @Test
    void testListNodeToString() {
        System.out.println(inputOutputList.getFirst().inputListNode.toString());
    }

    @Test
    void addTwoNumbers2() {
        for (int i = 0; i < inputOutputList.size(); i++) {
            InputOutput inputOutput = inputOutputList.get(i);
            ListNode listNode = solution.addTwoNumbers2(inputOutput.inputListNode, inputOutput.inputListNode2);
            Assertions.assertEquals(StringUtils.reverse(inputOutput.resultListNode.toString()), StringUtils.reverse(listNode.toString()));
        }
    }

    @Test  
    void addTwoNumbers2deleteRedundantVar() {  
        for (int i = 0; i < inputOutputList.size(); i++) {  
            InputOutput inputOutput = inputOutputList.get(i);  
            ListNode listNode = solution.addTwoNumbers2deleteRedundantVar(inputOutput.inputListNode, inputOutput.inputListNode2);  
            Assertions.assertEquals(StringUtils.reverse(inputOutput.resultListNode.toString()), StringUtils.reverse(listNode.toString()));  
        }  
    }

    @Test
    void addTwoNumbers3() {
        for (int i = 0; i < inputOutputList.size(); i++) {
            InputOutput inputOutput = inputOutputList.get(i);
            ListNode listNode = solution.addTwoNumbers3(inputOutput.inputListNode, inputOutput.inputListNode2);
            Assertions.assertEquals(StringUtils.reverse(inputOutput.resultListNode.toString()), StringUtils.reverse(listNode.toString()));
        }
    }

    @Test  
    void addTwoNumbersRecursion() {  
        for (int i = 0; i < inputOutputList.size(); i++) {  
            InputOutput inputOutput = inputOutputList.get(i);  
            ListNode listNode = solution.addTwoNumbersRecursion(inputOutput.inputListNode, inputOutput.inputListNode2);  
            Assertions.assertEquals(StringUtils.reverse(inputOutput.resultListNode.toString()), StringUtils.reverse(listNode.toString()));  
        }  
    }

}

相关链接

OB links

[[取模和求余运算的不同]]

OB tags

#LeetCode #算法