📃 题目描述

题目链接：

• 剑指 Offer II 025. 链表中的两数相加 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 445. 两数相加 II - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例 2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

🔔 解题思路

最直观的想法，根据链表求出整数，然后直接将两个整数相加，最后把结果用链表表示。这种思路的最大的问题是没有考虑到整数有可能会溢出。当链表较长时，表示的整数很大，可能会超出int甚至long的范围，如果根据链表求出整数就有可能会溢出

解决这个问题的办法是把表示整数的链表反转。反转之后的链表的头节点表示个位数，尾节点表示最高位数。此时从两个链表的头节点开始相加，就相当于从整数的个位数开始相加。

在做加法时还需要注意的是进位。如果两个整数的个位数相加的和超过10，就会往十位数产生一个进位。在下一步做十位数相加时就要把这个进位考虑进去。

总体来说就是三步走：

1. 先把两个表示整数的链表反转
2. 再在两个反转之后的链表中逐个节点实现加法
3. 最后把表示和的链表反转

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
		
        // 1 先把两个表示整数的链表反转
        ListNode head1 = reverseList(l1);
        ListNode head2 = reverseList(l2);
        // 2 再在两个反转之后的链表中逐个节点实现加法
        ListNode reversedHead = addReversed(head1, head2);
        // 3 最后把表示和的链表反转
        return reverseList(reversedHead);
        
    }

    // 俩链表从前往后相加，并返回第一个节点
    private ListNode addReversed(ListNode head1, ListNode head2) {
        // 虚拟头节点
        ListNode dummy = new ListNode(0);
        // 工作指针
        ListNode cur = dummy;
        // 进位
        int carry = 0;

        while (head1 != null || head2 != null) {
            int sum = (head1 == null ? 0 : head1.val)
                      + (head2 == null ? 0 : head2.val)
                      + carry;
            
            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum - 10 : sum;

            cur.next = new ListNode(sum);
            cur = cur.next;

            head1 = head1 == null ? null : head1.next;
            head2 = head2 == null ? null : head2.next;
        }

        // 处理最后一个进位
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }

        return dummy.next;
    }

    private ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;
        ListNode pre = null;

        while (cur != null) {
            // 保存 cur 的后继节点
            ListNode successor = cur.next;

            // 更改 next 指针
            cur.next = pre;

            // 进入下一个节点
            pre = cur;
            cur = successor;
        }

        // 返回反转后链表的头节点
        return pre;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：