用鏈表代表2個數(shù)字，這2個數(shù)字相加的和用鏈表返回。
最高位在鏈表的head.

思路：

1.鏈表逆序

數(shù)字相加是從低位到高位的，然而鏈表中的數(shù)字是從高位指向低位。
所以涉及到鏈表的逆序。

逆序之后只需從head到tail把兩個鏈表的數(shù)字相加，再用一個int表示進位。

鏈表的逆序:
最左邊的數(shù)字逆序后應該是tail, 它的next指向null.
后面的數(shù)字每次都指向它的前一個數(shù)字。
所以用cur表示當前node, cur.next指向它前一個node,
然后cur移動到鏈表的下一節(jié)點，不停地把cur.next指向前一個node.

在把結(jié)果的數(shù)字一個一個地保存進結(jié)果的鏈表中時，
不斷地把新數(shù)字指向前一個數(shù)字，就實現(xiàn)了從低位到高位保存的效果。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode newHead = null;
        int carry = 0;

        l1 = reverseList(l1);
        l2 = reverseList(l2);

        while(l1 != null || l2 != null || carry > 0) {
            int num1 = (l1 != null ? l1.val : 0);
            int num2 = (l2 != null ? l2.val : 0);

            int sum = num1 + num2 + carry;
            int num = sum % 10;
            carry = sum / 10;

            ListNode cur = new ListNode(num);
            cur.next = newHead;
            newHead = cur;

            l1 = (l1 != null ? l1.next : null);
            l2 = (l2 != null ? l2.next : null);
        }
        return newHead;
    }

    ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        while(cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

2.Stack

如果不想用鏈表逆序，可以用Stack, 同樣可以達到逆序的效果，但是速度不及上面的快。文章來源地址http://www.zghlxwxcb.cn/news/detail-596737.html

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> st1 = new Stack<>();
        Stack<Integer> st2 = new Stack<>();
        ListNode res = null;
        int carry = 0;

        //相當于逆序鏈表
        while(l1 != null) {
            st1.push(l1.val);
            l1 = l1.next;
        }

        while(l2 != null) {
            st2.push(l2.val);
            l2 = l2.next;
        }

        while(!st1.empty() || !st2.empty() || carry > 0) {
            int num1 = st1.empty() ? 0 : st1.pop();
            int num2 = st2.empty() ? 0 : st2.pop();
            int sum = num1 + num2 + carry;
            int num = sum % 10;
            carry = sum / 10;

            ListNode cur = new ListNode(num);
            cur.next = res;
            res = cur;
        }

        return res;
    }

到了這里，關于leetcode 445. Add Two Numbers II（兩數(shù)相加）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！