LeetCode 445. Add Two Numbers II

Problem

LeetCode 445. Add Two Numbers II

1. 题目简述

给出两个链表，每个链表表示一个数字，链表中的每个元素表示每一位，从高到低，求两个链表加和（有进位）。例如：

Example:

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

2. 算法思路

类似的题目还有LeetCode 2. Add Two Numbers，注意此题是从高位到低位存储，而LeetCode2中是从低到高存储。

双指针 + Stack

如果我们从头开始遍历的话，发现是从最高位开始的，但是我们计算又不能从最高位开始计算，一定要从最低位开始，因此我们需要一种能够从后向前遍历的数据结构，我们选择stack。

我们这里有一点需要着重强调，在对链表进行赋值计算的时候，每次对ptr.next进行new，然后将ptr = ptr.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) {
         if (l1 == null) {
             return l2;
         }
         if (l2 == null) {
             return l1;
         }

         Stack<Integer> stack1 = new Stack(), stack2 = new Stack(), stack = new Stack();
         while (l1 != null) {
             stack1.push(l1.val);
             l1 = l1.next;
         }
         while (l2 != null) {
             stack1.push(l2.val);
             l2 = l2.next;
         }

         int flag = 0;
         while (!stack1.isEmpty() || !stack2.isEmpty() || flag != 0) {
             int value1 = stack1.isEmpty() ? 0 : stack1.pop();
             int value2 = stack2.isEmpty() ? 0 : stack2.pop();
             int value = (value1 + value2 + flag) % 10;
             flag = (value1 + value2 + flag) / 10;

             stack.push(value);
         }

         ListNode head = new ListNode(), ptr = head;
         while (!stack.isEmpty()) {
             ptr.next = new ListNode(stack.pop());
             ptr = ptr.next;
         }

         return head.next;
    }
}

双指针 + ArrayList

其实数字的存储不一定要用stack，用arraylist会更快。代码如下：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        List<Integer> num1 = new ArrayList();
        List<Integer> num2 = new ArrayList();
        ListNode ptr = l1;
        while (ptr != null) {
            num1.add(ptr.val);
            ptr = ptr.next;
        }
        ptr = l2;
        while (ptr != null) {
            num2.add(ptr.val);
            ptr = ptr.next;
        }

        ListNode head = new ListNode(0);
        // form back to start
        int ptr1 = num1.size() - 1, ptr2 = num2.size() - 1, flag = 0;

        while (ptr1 >= 0 || ptr2 >= 0 || flag == 1) {
            int value1 = ptr1 < 0 ? 0 : num1.get(ptr1).intValue();
            int value2 = ptr2 < 0 ? 0 : num2.get(ptr2).intValue();
            int value = (value1 + value2 + flag) % 10;
            flag = (value1 + value2 + flag) / 10;

            // 这里注意给head赋值的方式，因为是从后向前进行遍历的。
            head.val = value;
            ListNode temp = new ListNode(0);
            temp.next = head;
            head = temp;
            ptr1--;
            ptr2--;
        }

        return head.next;
    }
}