algorithn medium

    2. 两数相加

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) { val = x; }
    7.  * }
    8.  */
    9. class Solution {
    10.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    11.         if (l1 == null && l2 == null) {return null;}
    12.         int i1, i2;
    13.         if (l1 == null) {i1 = 0;} else {i1 = l1.val;}
    14.         if (l2 == null) {i2 = 0;} else {i2 = l2.val;}
    15.         ListNode node = new ListNode((i1 + i2) % 10);
    16.         if ((i1 + i2) / 10 != 0) {
    17.             // 有进位的情况, 考虑将后位节点的值加一即可
    18.             // 这符合题意, 但会改变原链表
    19.             // 由于最上面判断了 l1 l2 均为 null 的情况, 故这里肯定有一个不为 null
    20.             if (l1 != null){ if (l1.next != null) {l1.next.val++;} else {l1.next = new ListNode(1);} }
    21.             else { if (l2.next != null) {l2.next.val++;} else {l2.next = new ListNode(1);} }
    22.         }
    23.         node.next = addTwoNumbers(l1 == null ? null: l1.next, l2 == null ? null : l2.next);
    24.         return node;
    25.     }
    26. }

    笔记

    代码就不说了, 用了递归, 这里最关键的其实是 如果个位数加起来和 >=10, 那么给 l1 或 l2 中不为 null 的那一个的 next 的 val + 1.

    因为整数一个位最大为 9, 就算两个 9, 和为 18, 被小位数进 1 加起来最多还是 19, 不可能出现 20 (进 2 的情况).