Add Two Numbers II || LeetCode-445

Problem link： https://leetcode.com/problems/add-two-numbers-ii/#/description

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 8 -> 0 -> 7

<问题描述>

给定两个非负整形的非空链表，整数的每一位以正常的顺序存储在链表中

你可以假定两个整数都没有前导的零

给出的addTwoNumbers函数应该以链表形式返回两个整数的和

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 8 -> 0 -> 7

Approach #1 (利用reverse()函数反转链表)

Analysis

这道题是之前那道Add Two Numbers的拓展，可以看到这道题的最高位在链表的首位置，如果我们将链表反转一下，然后参考之前那道题的解决方法，问题就变得很容易了。关键在于如何实现链表反转函数reverse()。

Code

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null && l2 == null) {
        return null;
    }
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }

    l1 = reverse(l1); // 链表l1反转
    l2 = reverse(l2); // 链表l2反转
    // resultList, resultNode, resultNext必须初始化，否则编译不通过
    ListNode resultList = null; // 返回链表
    ListNode resultNode = null; // 头节点
    ListNode resultNext = null; // 每次新插入的节点
    int carry = 0; // 进位

    while(l1 != null && l2 != null) {
        resultNext = new ListNode(l1.val + l2.val + carry);
        carry = resultNext.val / 10; // 计算进位
        resultNext.val = resultNext.val % 10; // 计算该位的数值

        if (resultList == null) { // 头节点为空，即插入的节点为返回链表的第一个节点时
            resultNode = resultNext;
            resultList = resultNext;
        }
        else { // 头节点不为空
            resultNode.next = resultNext;
            resultNode = resultNext;
        }
        l1 = l1.next;
        l2 = l2.next;
    }

    while (l1 != null) { // 链表l1比链表l2长，处理链表l1的高位
        resultNext = new ListNode(l1.val + carry);
        carry = resultNext.val / 10;
        resultNext.val = resultNext.val % 10;
        resultNode.next = resultNext;
        resultNode = resultNext;
        l1 = l1.next;
    }

    while (l2 != null) { // 链表l2比链表l1长，处理链表l2的高位
        resultNext = new ListNode(l2.val + carry);
        carry = resultNext.val / 10;
        resultNext.val = resultNext.val % 10;
        resultNode.next = resultNext;
        resultNode = resultNext;
        l2 = l2.next;
    }

    if (carry > 0) { // 最高位产生进位，需要新建节点进行存储
        resultNext = new ListNode(carry);
        resultNode.next = resultNext;
    }
    return reverse(resultList); // 返回的链表进行反转操作后再返回
}

// 单链表实现反转操作函数
public ListNode reverse(ListNode current) {
    // initialization
    ListNode previousNode = null;
    ListNode nextNode = null;

    while (current != null) {
        // save the next node
        nextNode = current.next;
        // update the value of "next"
        current.next = previousNode;
        // shift the pointers
        previousNode = current;
        current = nextNode;
    }
    return previousNode;
}

Complexity

时间复杂度：O(n)

空间复杂度：O(1)O(n)

Approach #2 (利用栈的后进先出存储节点数据)

Analysis

这里题目要求不使用reverse()函数，反转链表而不修改链表顺序，还有一种方法是利用栈来转换。由于加法需要从最低位开始运算，而最低位在链表末尾，链表只能从前往后遍历，没法取到前面的元素，我们可以利用栈来保存所有的元素，然后利用栈的后进先出的特点就可以从后往前取数字了。

Code

public ListNode addTwoNumbers(ListNode l1, ListNode l2){
    Stack<integer> stack1 = new Stack<integer>();
    Stack<integer> stack2 = new Stack<integer>();

    if (l1 == null && l2 == null) {
        return null;
    }
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    while (l1 != null) {
        stack1.push(l1.val);
        l1 = l1.next;
    }
    while (l2 != null) {
        stack2.push(l2.val);
        l2 = l2.next;
    }

    // resultNode, resultCurrent必须初始化
    ListNode resultNode = new ListNode(0); // 头节点
    ListNode resultCurrent = new ListNode(0); // 每次新插入的节点
    int carry = 0; // 进位
    while (!stack1.isEmpty() && !stack2.isEmpty()) {
        resultCurrent = new ListNode(stack1.pop() + stack2.pop() + carry);
        carry = resultCurrent.val / 10; // 计算进位
        resultCurrent.val = resultCurrent.val % 10; // 计算该位的数值

        // 构建链表方法：每次新建的节点插在head位置之前(头插法？)
        resultCurrent.next = resultNode.next;
        resultNode.next = resultCurrent;
    }

    while (!stack1.isEmpty()) { // 链表l1比链表l2长，处理链表l1的高位
        resultCurrent = new ListNode(stack1.pop() + carry);
        carry = resultCurrent.val / 10;
        resultCurrent.val = resultCurrent.val % 10;
        resultCurrent.next = resultNode.next;
        resultNode.next = resultCurrent;
    }

    while (!stack2.isEmpty()) { // 链表l2比链表l1长，处理链表l2的高位
        resultCurrent = new ListNode(stack2.pop() + carry);
        carry = resultCurrent.val / 10;
        resultCurrent.val = resultCurrent.val % 10;
        resultCurrent.next = resultNode.next;
        resultNode.next = resultCurrent;
    }

    if (carry > 0) { // 最高位产生进位，需要新建节点进行存储
        resultCurrent = new ListNode(carry);
        resultCurrent.next = resultNode.next;
        resultNode.next = resultCurrent;
    }
    return resultNode.next;
}

Complexity

时间复杂度：O(n)

空间复杂度：O(1)O(n)