给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807
错误解法:
错误思路: 将数字读出来还原, 进行加法得到sum, 再拆分sum写入到新的链表中
错误原因: 大数字会导致内存溢出
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil || l2 == nil { return nil } l := new(ListNode) rst := l pow10 := func(a int) int { if a == 0 { return 1 } rst := 1 for i := 1; i <= a; i++ { rst *= 10 } return rst } getInt := func(l *ListNode) (int) { if l == nil { return 0 } nums := []int{} for l != nil { nums = append(nums, l.Val) l = l.Next } rst := 0 for k, v := range nums { rst += pow10(k) * v } return rst } rstNum := getInt(l1) + getInt(l2) rstArr := strconv.Itoa(rstNum) bits := len(rstArr) for i := 1; i <= bits; i++ { l.Val = rstNum / pow10(i-1) % 10 if i == bits { break } l.Next = new(ListNode) l = l.Next } return rst}
正确解法:
思路: 直接模拟加法过程
package mainimport "fmt"type ListNode struct { Val int Next *ListNode}/*输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807*///[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]//[5,6,4]func main() { l1 := new(ListNode) l2 := new(ListNode) tmp1 := l1 tmp2 := l2 nums1 := []int{3, 5, 2} nums2 := []int{5,6,4} for i := 0; i < len(nums1); i++ { tmp1.Val = nums1[i] if i == len(nums1)-1 { break } tmp1.Next = new(ListNode) tmp1 = tmp1.Next } for i := 0; i < len(nums2); i++ { tmp2.Val = nums2[i] if i == len(nums2)-1 { break } tmp2.Next = new(ListNode) tmp2 = tmp2.Next } fmt.Println(l2.getInt()) fmt.Println(l1.getInt()) l2 = addTwoNumbers(l1, l2) fmt.Println(l2.getInt())}func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil || l2 == nil { return nil } l := new(ListNode) l.Val = 0 tmp := l flag := 0 // flag标志位, 模拟加法中的进位加1 for { num := l1.Val + l2.Val + tmp.Val if num >= 10 { tmp.Val = num % 10 flag = 1 } else { tmp.Val = num } if l1.Next == nil && l2.Next == nil { break } l1 = l1.Next l2 = l2.Next if l1 == nil { l1 = new(ListNode) l1.Val = 0 } if l2 == nil { l2 = new(ListNode) l2.Val = 0 } tmp.Next = new(ListNode) if flag == 1 { tmp.Next.Val = 1 flag = 0 } else { tmp.Next.Val = 0 } tmp = tmp.Next } if flag == 1 { // 这个判断一定要加, 因为 5 + 5 返回 0,1 tmp.Next = new(ListNode) tmp.Next.Val = 1 } return l}func (l *ListNode) Length() int { if l == nil { return 0 } i := 0 for l != nil { l = l.Next i++ } return i}// 返回链表中的值func (l *ListNode) getInt() (int) { if l == nil { return 0 } nums := []int{} for l != nil { nums = append(nums, l.Val) l = l.Next } rst := 0 for k, v := range nums { rst += pow10(k) * v } return rst}// 返回10的几次方 <---- 大数字的情况下在这里首先溢出, 写在这里只为了测试用func pow10(a int) int { if a == 0 { return 1 } rst := 1 for i := 1; i <= a; i++ { rst *= 10 } return rst}
/* 字体问题: 有些分不清 l 和 1,建议复制到IDE中进行查看 */