445. Add Two Numbers II

Leetcode Linked List

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

分析

类似于2. Add Two Numbers，唯一的区别是这里的链表没有反转。首先让人想到的是可以反转两个链表(206. Reverse Linked List)，然后再相加，但是题目提示了最好不要修改链表。

既然不能原地修改链表，那么使用栈来反转链表是最直接的。

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Stack<Integer> l1Stack = new Stack<>();
    Stack<Integer> l2Stack = new Stack<>();
    Stack<ListNode> result = new Stack<>();
    // 反转传入链表
    while (l1 != null) {
        l1Stack.add(l1.val);
        l1 = l1.next;
    }
    while (l2 !=  null) {
        l2Stack.add(l2.val);
        l2 = l2.next;
    }
    // 链表求和
    int carry = 0;
    while (!l1Stack.isEmpty()  || !l2Stack.isEmpty() || carry != 0) {
        int nextVal = 0;
        nextVal += carry;
        if (!l1Stack.isEmpty()) nextVal += l1Stack.pop();
        if (!l2Stack.isEmpty()) nextVal += l2Stack.pop();
        if (nextVal > 9) {
            nextVal -= 10;
            carry = 1;
        } else carry = 0;
        result.add(new ListNode(nextVal));
    }
    // 反转结果
    ListNode cur = result.pop();
    ListNode root = cur;
    while (!result.isEmpty()) {
        cur.next = result.pop();
        cur = cur.next;
    }
    cur.next = null;
    return root;
}

或者干脆将原链表复制一份，然后反转链表后求和，求和完成后再反转链表

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // copy l1, l2
    ListNode l1s = copyList(l1);
    ListNode l2s = copyList(l2);
    // reverse list
    ListNode l1r = reverseList(l1s);
    ListNode l2r = reverseList(l2s);
    // add
    ListNode res = new ListNode(-1), cur = res;
    int carry = 0;
    while (l1r != null || l2r != null || carry != 0) {
        int nextVal = carry;
        if (l1r != null) {nextVal += l1r.val; l1r = l1r.next;}
        if (l2r != null) {nextVal += l2r.val; l2r = l2r.next;}
        if (nextVal > 9) {
            nextVal -= 10;
            carry = 1;
        } else carry = 0;
        cur.next = new ListNode(nextVal);
        cur = cur.next;
    }
    ListNode root = res.next;
    return reverseList(root);
}


private ListNode reverseList(ListNode l) {
    if (l == null) return null;
    ListNode prev = null, cur = l, next = cur.next;
    while (next != null) {
        // reverse
        cur.next = prev;
        // forward
        prev = cur;
        cur = next;
        next = next.next;
    }
    cur.next = prev;
    return cur;
}

private ListNode copyList(ListNode l) {
    ListNode copy = new ListNode(-1);
    ListNode cur = copy;
    while (l != null) {
        cur.next = new ListNode(l.val);
        l = l.next;
        cur = cur.next;
    }
    cur.next = null;
    return copy.next;
}