445 Add Two Numbers II

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

解释下题目：

就是两个链表分别对应两个数字，然后输出两个

1. 日常沙雕方法...

实际耗时：错误

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    int num1 = getIntFromListNode(l1);
    int num2 = getIntFromListNode(l2);
    int result = num1 + num2;
    System.out.println(result);
    int len = String.valueOf(result).length();
    ListNode res = new ListNode(0);
    ListNode fakeHead = res;
    for (int i = 0; i < len; i++) {
        res.next = new ListNode((int) String.valueOf(result).charAt(i) - '0');
        res = res.next;
    }
    return fakeHead.next;
}

private int getIntFromListNode(ListNode l) {
    int res = 0;
    while (l != null) {
        res = res * 10 + l.val;
        l = l.next;
    }
    return res;
}

  我的思路很简单嘛，那把两个链表转成数字，然后再把两个数字一加，最后把和拆成一个链表.....结果当然是错误的，因为数字可以大到int完全放不下.....

时间复杂度O(n)

空间复杂度O(1)

2. 利用特殊的数据结构存

实际耗时：3ms

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    LinkedList<Integer> stack1 = getStackFromListNode(l1);
    LinkedList<Integer> stack2 = getStackFromListNode(l2);
    int flag = 0;
    ListNode fakeHead = new ListNode(-1);
    while (!stack1.isEmpty() && !stack2.isEmpty()) {
        int num1 = stack1.pop();
        int num2 = stack2.pop();
        int res = num1 + num2 + flag;
        if (res > 9) {
            flag = 1;
            ListNode tmp = new ListNode(res - 10);
            tmp.next = fakeHead.next;
            fakeHead.next = tmp;
        } else {
            flag = 0;
            ListNode tmp = new ListNode(res);
            tmp.next = fakeHead.next;
            fakeHead.next = tmp;
        }
    }
    while (!stack1.isEmpty()) {
        int num1 = stack1.pop();
        int res = num1 + flag;
        if (res > 9) {
            flag = 1;
            ListNode tmp = new ListNode(res - 10);
            tmp.next = fakeHead.next;
            fakeHead.next = tmp;
        } else {
            flag = 0;
            ListNode tmp = new ListNode(res);
            tmp.next = fakeHead.next;
            fakeHead.next = tmp;
        }
    }

    while (!stack2.isEmpty()) {
        int num2 = stack2.pop();
        int res = num2 + flag;
        if (res > 9) {
            flag = 1;
            ListNode tmp = new ListNode(res - 10);
            tmp.next = fakeHead.next;
            fakeHead.next = tmp;
        } else {
            flag = 0;
            ListNode tmp = new ListNode(res);
            tmp.next = fakeHead.next;
            fakeHead.next = tmp;
        }
    }

    if (flag == 1) {
        ListNode tmp = new ListNode(1);
        tmp.next = fakeHead.next;
        fakeHead.next = tmp;
    }

    return fakeHead.next;
}

private LinkedList<Integer> getStackFromListNode(ListNode l) {
    LinkedList<Integer> stack = new LinkedList<>();
    while (l != null) {
        stack.push(l.val);
        l = l.next;
    }
    return stack;
}

  思路就是先用栈存起来，然后取出来进行操作，只是我现在写的代码还是不够简洁啊，其实三部分可以合三为一。

时间复杂度O(n)

空间复杂度O(n)