我的吉米城: [LeetCode] Add Two Numbers 兩LinkedList相加 (No.2)

2016/7/14

[LeetCode] Add Two Numbers 兩LinkedList相加 (No.2)

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

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/

Ref: https://leetcode.com/problems/add-two-numbers/
中文簡單說明：
給你兩組LinkedList，其中每個節點裡面有著非負數(可能零或正數)的數字，以及下個節點為何，要注意的是這兩組節點是相反的節點，我們在求他們的和要特別注意，另外，如果超過十就要進位。

解法：
因為對LinkedList不太熟，從例子當中也看不太出來詳細分解步驟，於是直接找了其他人寫的程式碼來閱讀，並做出自己的理解。
Ref: https://discuss.leetcode.com/topic/42252/concise-java-solution-beats-98-with-comment/2
閱讀過後，發現他是先做了一個假的頭，並且把後面算出來的答案放入最後面的節點中的NEXT裡，並把尾巴的指標指向新的節點這樣就可以一一求得解了。真的是很不錯的做法。
不過要注意的是，裡面在取Number1的值時，忘了加上檢查，所以會出現NullPointerException的錯誤，這部份我已在我的程式碼當中修復了。

部份程式碼：

	// Ref:
	// https://discuss.leetcode.com/topic/42252/concise-java-solution-beats-98-with-comment/2
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	if (l1 == null)
	return l2;
	if (l2 == null)
	return l1;

	int carry = 0;
	// 建立一個假頭，由這邊開始作業，也因為是假頭，使用題目中不會出現的-1表示
	ListNode fakeHead = new ListNode(-1);
	// 把尾巴的位置指向假頭
	ListNode tail = fakeHead;

	while (carry > 0 \|\| l1 != null \|\| l2 != null) { // check if next node
	// exsits
	int n1 = l1 == null ? 0 : l1.val; // get value of number 1
	// 進行判斷，要不然會出現NullPointerException
	if (l1 != null)
	l1 = l1.next;

	int n2 = l2 == null ? 0 : l2.val; // get value of number 2
	// 進行判斷，要不然會出現NullPointerException
	if (l2 != null)
	l2 = l2.next;

	int sum = n1 + n2 + carry;
	// 計算出需進位多少
	carry = sum / 10;

	// 求出不需進位的部份並建立出新的ListNode
	ListNode cur = new ListNode(sum % 10);
	// 把新ListNode放入NEXT的欄位中
	tail.next = cur;
	// 將尾巴指向新ListNode的位置，以便後面進行處理再加入新的ListNode
	tail = cur;
	}
	return fakeHead.next;
	}