2. Add Two Numbers (medium)
2.1.png
- 指針的用處:
- 判斷是否到達(dá)鏈表結(jié)尾
- 在一個(gè)已存在的鏈表上移動(dòng)指針,一定要先判斷當(dāng)前指針是否指向null
- 兩數(shù)相加,切記要加上進(jìn)位(0或1),從個(gè)位開始處理
- 10進(jìn)制加法,每一位的范圍是[0,9],進(jìn)位放到更高一位上.這是兩個(gè)約束
- Complexity analysis:
- time complexity: O(max(link1,link2))
- space complexity: O(max(link1,link2))
-
圖示如下,很直觀,用一個(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. 申請空間:存儲(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;
}
}
