剑指 Offer II 025. 链表中的两数相加

迭代

栈

1. 创建两个栈，分别将链表 1 和链表 2 都加入栈中
2. 弹出栈计算即可得到正确的链表

反转链表

1. 反转链表完成后，就是简单的大数相加问题

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) return l1 == null ? l2 : l1;
        ListNode newL1 = reverse(l1);
        ListNode newL2 = reverse(l2);
        int carry = 0;
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (newL1 != null || newL2 != null) {
            int newVal = 0;
            newVal += newL1 == null ? 0 : newL1.val;
            newVal += newL2 == null ? 0 : newL2.val;
            newVal += carry;
            carry = newVal / 10;
            newVal = newVal % 10;
            p.next = new ListNode(newVal);
            p = p.next;
            newL1 = newL1 == null ? null : newL1.next;
            newL2 = newL2 == null ? null : newL2.next;
        }
        if (carry != 0) {
            p.next = new ListNode(carry);
        }
        return reverse(dummy.next);
    }
    private ListNode reverse(ListNode head) {
        ListNode prev = null, p = head;
        while (p != null) {
            ListNode next = p.next;
            p.next = prev;
            prev = p;
            p = next;
        }
        return prev;
    }
}