2. 两数相加

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)  
输出：7 -> 0 -> 8  
原因：342 + 465 = 807

解法

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	h := &ListNode{}
	for s := h; l1 != nil; l1 = l1.Next {
		s.Val = l1.Val
		if l1.Next != nil {
			s.Next = &ListNode{}
		}
		s = s.Next
	}
	k := 0
	s, e := h, h
	for l2 != nil {
		s.Val += l2.Val + k
		k = 0
		if s.Val >= 10 {
			s.Val -= 10
			k = 1
		}
		if s.Next == nil {
			s.Next = &ListNode{}
		}
		e = s
		s = s.Next
		l2 = l2.Next
	}
	for k != 0 && s != nil {
		s.Val += k
		k = 0
		if s.Val >= 10 {
			s.Val -= 10
			k = 1
		}
		s = s.Next
		e = e.Next
	}
	if k != 0 {
		if s != nil {
			e.Next.Val += 1
		} else {
			e.Next = &ListNode{Val: 1}
		}
	}
	for s != nil {
		if s.Val == 0 && s.Next == nil {
			e.Next = nil
		}
		s = s.Next
		e = e.Next
	}
	return h
}

本地测试

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func print(h *ListNode) {
	for h != nil {
		fmt.Print(h.Val)
		h = h.Next
	}
	fmt.Println()
}

func main() {
	l1 := ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3}}}
	l2 := ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4}}}
	print(addTwoNumbers(&l1, &l2))
	l1 = ListNode{Val: 0}
	l2 = ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4}}}
	print(addTwoNumbers(&l1, &l2))
	l1 = ListNode{Val: 9, Next: &ListNode{Val: 9}}
	l2 = ListNode{Val: 9}
	print(addTwoNumbers(&l1, &l2))
	l1 = ListNode{Val: 8, Next: &ListNode{Val: 9, Next: &ListNode{Val: 9}}}
	l2 = ListNode{Val: 2}
	print(addTwoNumbers(&l1, &l2))
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers