Add Two numbers

。題目假設

給兩個鏈表，各自代表一個整數，求相加的結果

。重要問題

如果先將鏈表變為整數 -> 相加 -> 再轉為鏈表，有可能會溢位，就算用 long 也有問題，可能是一個超長整數！

。直覺

先將鏈表變為整數 -> 相加 -> 再轉為鏈表

。解決方法可行性

失敗，因為可能是超長整數，所以只能用鏈表相加，然後要注意進位

。解決方案

用鏈表相加

。資料結構

linked list

。複雜度

O(n)

。遇到的困難點、想錯的地方

這題考點大概是整數溢位，要跟出題者討論清楚

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null)
        return new ListNode(-1);

    int extra = 0;
    ListNode head = new ListNode(-1);
    ListNode cur = new ListNode(-1);
    while (l1 != null || l2 != null)
    {
        int sum = 0;
        if (l1 != null && l2 != null) {
            sum = l1.val+l2.val+extra;
            l1 = l1.next;
            l2 = l2.next;
        }
        else if (l1 == null && l2 != null) {
            sum = extra + l2.val;
            l2 = l2.next;
        } 
        else {
            sum = extra + l1.val; 
            l1 = l1.next;
        }

        extra = sum / 10;
        sum = sum % 10;
        ListNode newNode = new ListNode(sum);
        if (head.next == null)
        {
            head.next = newNode;
            cur = head.next;
        }
        else {
            cur.next = newNode;
            cur = cur.next;
        }
    }
    if (extra != 0)
        cur.next = new ListNode(extra);

    return head.next;
}