leetcode - 2. Add Two Numbers－Lung-Yu,Tsai 的部落格

題目:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

思路:

簡單講就是將兩個當向鏈結串列的數值進行相加.

關鍵點是操作單向鏈結串列,其中家法過程中可能產生進位,因此需要注意.

由於若數值過大會導致超出整數最大值而崩潰,因此採用即時運算每個數值,其中直接利用sum的相加與除法控制進位數值.

line 26 為避免剛好有進位,透過loop將其進位確實的加入array之中.

此處使用array儲存每個數值目的是為方便後續回傳單向鏈結串列時,重組資料方便.

透過reverse the array 即可輕易重組資料.

/**
 * 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) {
        int sum = 0,unit = 1;
        ArrayList<Integer> array = new ArrayList<Integer>(); 
        while(l1!=null || l2!=null){
            if(l1!=null){
                sum += l1.val * unit;
                l1 = l1.next;
            }
            if(l2!=null){
                sum += l2.val * unit;
                l2 = l2.next;
            }
            array.add(sum%10);
            sum /= 10;
        }
    
        while(sum > 0){
            array.add(sum%10);
            sum /= 10;
        }
        
        Collections.reverse(array);
        
        ListNode node =null;
        for(int v : array){
            System.out.println(v);
            ListNode temp = new ListNode(v);
            temp.next = node;
            node = temp;
        }
       
        
        return node;
    }
}