Welcome To My Blog

2. Add Two Numbers (medium)

2.1.png

1. 指針的用處:
   • 判斷是否到達(dá)鏈表結(jié)尾
   • 在一個(gè)已存在的鏈表上移動(dòng)指針,一定要先判斷當(dāng)前指針是否指向null
2. 兩數(shù)相加,切記要加上進(jìn)位(0或1),從個(gè)位開始處理
3. 10進(jìn)制加法,每一位的范圍是[0,9],進(jìn)位放到更高一位上.這是兩個(gè)約束
4. Complexity analysis:
   • time complexity: O(max(link1,link2))
   • space complexity: O(max(link1,link2))

5. 圖示如下,很直觀,用一個(gè)額外的ListNode作為結(jié)果鏈表的開始

   
   
   2.2.png

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
public ListNode addTwoNumbers(ListNode l1,ListNode l2) {
    //1. 這個(gè)節(jié)點(diǎn)作為結(jié)果鏈表的開始
    ListNode resHead = new ListNode(0); 
    //2. 指針
    ListNode p = l1, q = l2, curr = resHead;
    //3. 加法的進(jìn)位
    int carry = 0; 
    //4. 通過指針是否為空判斷是否遍歷完鏈表
    while(p != null || q!=null){ 
        //5. 如果p沒指向null則返回當(dāng)前ListNode的值,否則返回0
        int x = (p !=null)? p.val : 0; 
        int y = (q != null)? q.val : 0;
        //6. 加進(jìn)位! 加進(jìn)位! 加進(jìn)位!
        int sum = x+y+carry;//最開始誤寫成x+y,漏了carry
        carry = sum/10;  
        //7. 申請(qǐng)空間:存儲(chǔ)計(jì)算結(jié)果;指向下一個(gè)節(jié)點(diǎn)
        //7.1 約束:每一位的范圍是[0,9]!!!
        curr.next = new ListNode(sum%10); 
        curr = curr.next;
        //8. 不能直接移動(dòng)指針,可能會(huì)造成java.lang.NullPointerException,得加if判斷當(dāng)前p是不是null;指針可以指向空,但是空指針沒有.next
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    //9. 看看最后的兩個(gè)數(shù)相加的結(jié)果,如果還有進(jìn)位就得再建立個(gè)ListNode
    if (carry > 0) { 
        curr.next = new ListNode(carry);
    }
    return resHead.next;
}
}