Day.9 Add Two Numbers

Leetcode #2. Add Two Numbers

简单来说就是要做两个链结的加总

ex.1
Input: list 1: 2->4->3, list 2: 5->6->4
Output: [7,0,8]
342 + 465 = 807 (个位数在链结的最左边)

如果你没做过这题，强烈建议你先思考一下怎麽解。

防雷
防雷
防雷

这一题主要让你熟悉链结的操作，只要搞懂了链结，花点时间就可以写出来。
只要每一次加总，处理一下进位，应该就可以解决了，时间复杂度为O(n)

程序:

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	node := &ListNode{}
	temp := node
	curry := 0 // 记录有没有进位

	for {
        // 两个链结长度可能不一样，只要一边有东西，还是要加总下去
		if l1 == nil && l2 == nil {
			break
		}

		num := 0
		if l1 != nil {
			num += l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			num += l2.Val
			l2 = l2.Next
		}

        // 判断进位
		num += curry
		if num >= 10 {
			num = num % 10
			curry = 1
		} else {
			curry = 0
		}

		temp.Next = &ListNode{
			Val: num,
		}
		temp = temp.Next
	}

	if curry == 1 {
		temp.Next = &ListNode{
			Val: 1,
		}
	}

	return node.Next
}

明天来讲Queue & Stack！