README.md

title	subtitle	date	lastmod	draft	author	authorLink	description	license	images	tags	categories	featuredImage	featuredImagePreview	hiddenFromHomePage	hiddenFromSearch	twemoji	lightgallery	ruby	fraction	fontawesome	linkToMarkdown	rssFullText	toc	code	math	mapbox	share	comment	library	seo
0002.Add Two Numbers	https://leetcode.com/problems/add-two-numbers/description/	2024-03-02 15:57:00 +0800	2024-03-02 15:57:00 +0800	false	Kimi.Tsai	https://kimi0230.github.io/	0002.Add-Two-Numbers			LeetCode Go Medium Add Two Numbers Linked List Math Recursion Amazon Apple Facebook Microsoft Bloomberg	LeetCode			false	false	false	true	true	true	true	false	false	enable auto true true	copy maxShownLines true 200	enable		enable true	enable true	css js	images

0002.Add Two Numbers

題目

題目大意

解題思路

鏈表雙指標技巧 和加法運算過程中對進位的處理。 注意這個 carry 變數的處理，在我們手動類比加法過程的時候會經常用到。

• 遍歷 l1跟 l2. 講兩個list的val相加, 並且記錄進位的值給next使用
• 最後如果 carry 還有的話, 需要產生一個新的節點

Big O

• 時間複雜 : O(max⁡(m,n) 時間複雜度： O(max⁡(m,n)) ，其中 m 和 n 分別為兩個鏈表的長度。 我們要遍歷兩個鏈表的全部位置，而處理每個位置只需要 O(1) 的時間

• 空間複雜 : O(1) O(1) 。 注意返回值不計入空間複雜度

來源

• https://leetcode.com/problems/add-two-numbers/description/
• https://leetcode.cn/problems/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0002.Add-Two-Numbers/main.go

package addtwonumbers

// 時間複雜 O(max(m,n)), 空間複雜 O(1)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// 遍歷 l1跟 l2. 講兩個list的val相加, 並且記錄進位的值給next使用
// 最後如果 carry 還有的話, 需要產生一個新的節點
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var result, tail *ListNode
	carry := 0
	for l1 != nil || l2 != nil {
		n1, n2 := 0, 0
		if l1 != nil {
			n1 = l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			n2 = l2.Val
			l2 = l2.Next
		}
		sum := n1 + n2 + carry
		sum, carry = sum%10, sum/10

		if result == nil {
			result = &ListNode{Val: sum, Next: nil}
			tail = result
		} else {
			tail.Next = &ListNode{Val: sum, Next: nil}
			tail = tail.Next
		}
	}
	// 最後如果 carry 還有的話, 需要產生一個新的節點
	if carry > 0 {
		tail.Next = &ListNode{Val: carry, Next: nil}
	}
	return result
}

Benchmark