【LeetCode】2. 两数相加

难度

中等

题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

解答

基础思路： 顺序读取链表，从链表中将val值倒序的方式读成字符串。 因为链表结构，不能进行数值计算，因此需要实现一个字符串加法计算。

package main

import (
	"errors"
	"fmt"
	"strconv"
)

func main() {
	list1 := &ListNode{
		Val: 9,
		Next: &ListNode{
			Val: 9,
			Next: &ListNode{
				Val: 9,
				Next: &ListNode{
					Val: 9,
					Next: &ListNode{
						Val:  9,
						Next: nil,
					},
				},
			},
		},
	}
	list2 := &ListNode{
		Val: 9,
		Next: &ListNode{
			Val: 9,
			Next: &ListNode{
				Val:  9,
				Next: nil,
			},
		},
	}

	result := addTwoNumbers(list1, list2)

	printLinkNode(list1)
	printLinkNode(list2)
	printLinkNode(result)
}

//单项链表
type ListNode struct {
	Val  int
	Next *ListNode
}

var f func(str string, sumNode *ListNode) *ListNode
var r func(str string, node *ListNode) string

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	str1, _ := parseLinkNode(l1)
	str2, _ := parseLinkNode(l2)

	sumStr := strSum(str1, str2)
	sumNode := &ListNode{}

	f = func(str string, sumNode *ListNode) *ListNode {
		if len(str) <= 0 {
			return nil
		}
		sumNode.Val, _ = strconv.Atoi(string(str[0]))

		newNode := &ListNode{}
		sumNode.Next = f(str[1:], newNode)
		return sumNode
	}

	return f(sumStr, sumNode)
}

//两个字符串相加
func strSum(str1, str2 string) string {
	maxLen := len(str1)
	if len(str2) > len(str1) {
		maxLen = len(str2)
	}
	var carry bool
	var result string
	for i := 0; i < maxLen; i++ {
		var n1, n2 int
		if i < len(str1) {
			n1, _ = strconv.Atoi(string(str1[i]))
		}
		if i < len(str2) {
			n2, _ = strconv.Atoi(string(str2[i]))
		}

		s := n1 + n2
		if carry {
			s++
			carry = false
		}
		if s < 10 {
			result += strconv.Itoa(s)
		} else {
			result += strconv.Itoa(s - 10)
			carry = true
		}
	}
	if carry {
		result += "1"
	}
	return result
}

//解析链表，将Val拼接成字符串
func parseLinkNode(node *ListNode) (string, error) {
	if node == nil {
		return "", errors.New("EmptyNode")
	}
	var str string
	r = func(str string, node *ListNode) string {
		str += strconv.Itoa(node.Val)
		if node.Next != nil {
			return r(str, node.Next)
		}
		return str
	}
	return r(str, node), nil
}

func printLinkNode(node *ListNode) {
	if node == nil {
		return
	}
	if node.Next != nil {
		fmt.Print(node.Val, ",")
		printLinkNode(node.Next)
	} else {
		fmt.Print(node.Val)
	}
	fmt.Println()
}

提交结果：

• 耗时：12 ms
• 内存：5.1 MB