未分類

Add Two Numbers

Go, LeetCode, LinkedList, Math

Add Two Numbers

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.

For Example:

1
2
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
提示 解題應用
LinkedList Pointer
Math 規律觀查

Default:

1
2
3
4
5
6
7
8
9
10
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
}

解答思路:

一開始本來是分別遍歷兩個LinkedList，在各別算出兩個數字做總合，最後才生成新的LinkedList做回傳，不過因為LinkedList會極長就沒辦法這樣搞，而且這樣也太浪費時間，所以就是同時一起對兩個LinkedList做遍歷，並將結果取代其一LinkedList的值，如果兩節點做總合時有進位的情況，就將進位的數字加到下一組做節點總合，又如果有其中一方的LinkedList較短先結束，這時就將另一方尚未遍歷完成的LinkedList接在其後頭，此時只要繼續判斷是否要進位到下一個節點即可，沒有的話就可以直接回傳整個合併的LinkedList，有的話才進到下一個節點並+1再次做判斷，最後若已經遍歷結果了，然而仍需進位的情況發生，這時就要在最後自行新增一個新的節點在LinkedList的最後頭，而其值當然必為1。

程式碼解說:

因為我們是將總合的結果值取代原本的節點值，而且也是回傳原本的LinkedList回去，所以一開始我們就以第一個LinkedList為主，並記錄其第一個節點的位置用以結果回傳，接下來就開始同時遍歷兩個LinkedList的節點，其中任一LinkedList先為nil才停止遍歷，一邊遍歷兩LinkedList的同時，一邊將分別將兩個節點值做總合，並將總合的結果除以10取於餘數並取代第一個LinkedList節點的值，至先前除完的商如果大於0(有進位)自然就會繼續往下一組節點的總合做累加，完成之後才又同時將兩LinkedList遍歷的節點下移，不過在此之前要先暫存第一個LinkedList遍歷完的位置，因為如果是該LinkedList先結束而稍後就需要將另一尚未遍歷過LinkedList的後半部給嫁接在後頭，此時就需要知道先前遍歷完的最後一個節點位置才有辦法進行嫁接

1
2
3
4
5
6
7
8
9
10
11
var sum int
var tmp *ListNode
result := l1
for l1 != nil && l2 != nil {
	sum += l1.Val + l2.Val
	l1.Val = sum % 10
	sum /= 10
	tmp = l1
	l1 = l1.Next
	l2 = l2.Next
}

如果是第一個LinkedList不為nil，那麼就沒有問題可以直接繼續遍歷，因為我們就是以第一個LinkedList為主，但如果是第二個LinkedList不為nil，表示第一個LinkedList已經遍歷完了，這時就要將前一步暫存l1的最後一個節點位置與l2尚位遍歷的節點先做嫁接，在嫁接結束後剩下的部分不管前述哪種情況都是處理進位與尚未遍歷過部分的關係，如果合併後的LinkedList不為nil且進位值大於0則繼續往下一個節點的值累加，與先前類似將總合與節點值相加，接著將總合與10取餘數取代節點值，最後如果商大於0才往下累加，這次也一樣需要先暫存最後一個節點的位置才往下移動

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if l1 != nil {
	for l1 != nil && sum > 0 {
		sum += l1.Val
		l1.Val = sum % 10
		sum /= 10
		tmp = l1
		l1 = l1.Next
	}
} else if l2 != nil {
	tmp.Next = l2
	for l2 != nil && sum > 0 {
		sum += l2.Val
		l2.Val = sum % 10
		sum /= 10
		tmp = l2
		l2 = l2.Next
	}
}

如果所有節點都遍歷結束，然而總合的值仍大於0表示還有進位，這時就需要自行新增一個新的節點其值為1到整個LinkedList的最後頭，最後才將整串節點也就是在最一開始所存第一個LinkedList的第一個節點位置給回傳

1
2
3
4
if sum > 0 {
	tmp.Next = &ListNode{1, nil}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var sum int
	var tmp *ListNode
	result := l1
	for l1 != nil && l2 != nil {
		sum += l1.Val + l2.Val
		l1.Val = sum % 10
		sum /= 10
		tmp = l1
		l1 = l1.Next
		l2 = l2.Next
	}
	if l1 != nil {
		for l1 != nil && sum > 0 {
			sum += l1.Val
			l1.Val = sum % 10
			sum /= 10
			tmp = l1
			l1 = l1.Next
		}
	} else if l2 != nil {
		tmp.Next = l2
		for l2 != nil && sum > 0 {
			sum += l2.Val
			l2.Val = sum % 10
			sum /= 10
			tmp = l2
			l2 = l2.Next
		}
	}
	if sum > 0 {
		tmp.Next = &ListNode{1, nil}
	}
	return result
}

總結:

給予兩個LinkedList，其中同個LinkedList每個節點值表示數字的每一進位，並需要將此兩LinkedList表示的數字做總合，且也要回傳一個LinkedList，最佳的做法就是同時一起對兩個LinkedList做遍歷，並將結果取代其一LinkedList的值，如果兩節點做總合時有進位的情況，就將進位的數字加到下一組做節點總合，又如果有其中一方的LinkedList較短先結束，這時就將另一方尚未遍歷完成的LinkedList接在其後頭，此時只要繼續判斷是否要進位到下一個節點即可，沒有的話就可以直接回傳整個合併的LinkedList，有的話才進到下一個節點並+1再次做判斷，最後若已經遍歷結果了，然而仍需進位的情況發生，這時就要在最後自行新增一個新的節點在LinkedList的最後頭，而其值當然必為1。

分享到