[LeetCode] Add Two Numbers

[LeetCode] Add Two Numbers

You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

(1) 將兩個鏈表轉化成數字，然後數字運算，然後再轉成鏈表：

我覺得這也是一種思路，雖然運算麻煩點，但是思路簡單。

但注意：整數運算很容易超出范圍，導致返回錯誤結果。所以我們拿double或者float來接受數字就好了。但是在判斷的時候，必須用while(num>=1)來判斷是否已經將num的數取完。因為整數會自動取整，float和double要手動處理下。

在時間復雜度上，要比（2）耗時一點，不過也是 O(n)時間.

（2）從兩個鏈表頭遍歷到尾，用一個carry常量來代表進位，既然是逆序排列，我們就直接遍歷就好了。

但是有一點要注意，就是題目並沒有說兩個鏈表是一樣的長度，那我們如同mergesort那樣，把多余的那一截，加上進位進行運算。

最後還得判斷下：如果carry還是等於1，那說明新的數字要比之前的數多一位。 比如99999+1這樣的。所以這種情況，再加上一個1節點即可。

代碼重復的地方有點多，應該可以把後面兩個while優化一下，整合到一起。但是思路是沒有問題的。

O（n）時間 leetcode一次通過。

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		if (l1 == null && l2 == null)
			return null;
		double num1 = ListToNumber(l1);
		double num2 = ListToNumber(l2);
		return NumberToList(num1 + num2);
	}

	public static ListNode NumberToList(double num) {
		ListNode head = new ListNode(0);
		ListNode res = head;
		if (num < 10)
			return new ListNode((int) num);
		while (num >= 1) {
			int lastdigit = (int) (num % 10);
			num = num / 10;
			head.next = new ListNode(lastdigit);
			head = head.next;
		}
		return res.next;
	}

	public static double ListToNumber(ListNode head) {
		if (head == null)
			return 0;
		double num = 0;
		double base = 1;
		while (head != null) {
			num += head.val * base;
			head = head.next;
			base = base * 10;
		}
		return num;
	}

Solution 2（推薦）

     public  ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	        if(l1==null && l2==null) return null;
	        ListNode res=new ListNode(1);
	        ListNode dummy=res;
	        int carry=0;
	        while(l1!=null && l2!=null){
	            int val=l1.val+l2.val+carry;
	            if(val>9){
	                val=val%10;
	                carry=1;
	            } else {
	                carry=0;
	            }
	            res.next=new ListNode(val);
	            res=res.next;
	            l1=l1.next;
	            l2=l2.next;
	        }
	        
	        while(l1!=null){
	            int val=l1.val+carry;
	            if(val>9){
	                val=val%10;
	                carry=1;
	            } else {
	                carry=0;
	            }
	            res.next=new ListNode(val);
	            res=res.next;
	            l1=l1.next;
	        }
	        
	        while(l2!=null){
	            int val=l2.val+carry;
	            if(val>9){
	                val=val%10;
	                carry=1;
	            } else {
	                carry=0;
	            }
	            res.next=new ListNode(val);
	            res=res.next;
	            l2=l2.next;
	        }
	        
	        if(carry==1){
	            res.next=new ListNode(1);
	        }
	        
	        return dummy.next;
	        
	    }