Welcome To My Blog

2. Add Two Numbers (medium)

2.1.png

1. 指针的用处:
   • 判断是否到达链表结尾
   • 在一个已存在的链表上移动指针,一定要先判断当前指针是否指向null
2. 两数相加,切记要加上进位(0或1),从个位开始处理
3. 10进制加法,每一位的范围是[0,9],进位放到更高一位上.这是两个约束
4. Complexity analysis:
   • time complexity: O(max(link1,link2))
   • space complexity: O(max(link1,link2))

5. 图示如下,很直观,用一个额外的ListNode作为结果链表的开始

   
   
   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. 这个节点作为结果链表的开始
    ListNode resHead = new ListNode(0); 
    //2. 指针
    ListNode p = l1, q = l2, curr = resHead;
    //3. 加法的进位
    int carry = 0; 
    //4. 通过指针是否为空判断是否遍历完链表
    while(p != null || q!=null){ 
        //5. 如果p没指向null则返回当前ListNode的值,否则返回0
        int x = (p !=null)? p.val : 0; 
        int y = (q != null)? q.val : 0;
        //6. 加进位! 加进位! 加进位!
        int sum = x+y+carry;//最开始误写成x+y,漏了carry
        carry = sum/10;  
        //7. 申请空间:存储计算结果;指向下一个节点
        //7.1 约束:每一位的范围是[0,9]!!!
        curr.next = new ListNode(sum%10); 
        curr = curr.next;
        //8. 不能直接移动指针,可能会造成java.lang.NullPointerException,得加if判断当前p是不是null;指针可以指向空,但是空指针没有.next
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    //9. 看看最后的两个数相加的结果,如果还有进位就得再建立个ListNode
    if (carry > 0) { 
        curr.next = new ListNode(carry);
    }
    return resHead.next;
}
}