445. 两数相加 II

本题来自 LeetCode：445. 两数相加 II^[1]

题目描述

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:

输入: (7 - 2 - 4 - 3) + (5 - 6 - 4)
输出: 7 - 8 - 0 - 7

解法一

题目分析

可以先对两个链表进行反转，然后按照 2. 两数相加处理即可；

题目解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        // 反转链表l1
        l1 = reverse(l1);
        // 反转链表l2
        l2 = reverse(l2);

        ListNode cur = dummy;
        int carry = 0;
        while(carry != 0 || l1 != null || l2 != null) {
            int digit1 = 0;
            if(l1 != null) {
                digit1 = l1.val;
                l1 = l1.next;
            }
            int digit2 = 0;
            if(l2 != null) {
                digit2 = l2.val;
                l2 = l2.next;
            }
            carry += digit2 + digit1;
            cur.next = new ListNode(carry % 10);
            cur = cur.next;
            carry /= 10;
        }
        // 反转结果
        return reverse(dummy.next);
    }

    public ListNode reverse(ListNode list) {
        ListNode dummy = new ListNode(-1);
        while(list != null) {
            ListNode node = list.next;
            list.next = dummy.next;
            dummy.next = list;
            list = node;
        }
        return dummy.next;
    }
}

复杂度分析：
时间复杂度： O(m + n)
空间复杂度： O(m + n)

解法二

题目分析

进阶注意点中，提到不能修改原链表， 那么要想先处理尾节点，那么就需要用先进后出的数据结构，可以采用栈，对两个链表进行入栈处理。

题目解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StackInteger stack1 = new Stack();
        StackInteger stack2 = new Stack();
        // l1每个元素入栈
        while(l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        // l2每个元素入栈
        while(l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }

        ListNode dummy = new ListNode(-1);
        int carry = 0;
        // 相加
        while(carry != 0 || !stack1.isEmpty() || !stack2.isEmpty()) {
            int digit1 = stack1.isEmpty() ? 0 : stack1.pop();
            int digit2 = stack2.isEmpty() ? 0 : stack2.pop();
            carry += digit1 + digit2;
            ListNode node = new ListNode(carry % 10);
            carry /= 10;
            node.next = dummy.next;
            dummy.next = node;
        }

        return dummy.next;
    }
}

复杂度分析：
时间复杂度： O(m + n)
空间复杂度： O(m + n)

参考资料

445. 两数相加 II: https://leetcode-cn.com/problems/add-two-numbers-ii

原文始发于微信公众号（xiaogan的技术博客）：