难度
中等
题目
给你两个 非空
的链表,表示两个非负的整数。它们每位数字都是按照 逆序
的方式存储的,并且每个节点只能存储 一位
数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 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
评论区