Loveyless的学习笔记

Appearance

Return to top
On this page

想法

初步觉得需要操作一下数组 转数字 在加一下转回去

题目都不太懂

因为学前端没解除过链表 数据结构光学二叉树了(虽然我还没好好听)但是幸运的是正好买了本算法小册 懂了链表 回头再来刷这道题 看了一下解析 明白了

go
type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	return nil
}

func main() {  //这样就叫链表
	l1 := ListNode{2, &ListNode{4, &ListNode{4, &ListNode{3, nil}}}}
	l2 := ListNode{5, &ListNode{6, &ListNode{4, &ListNode{3, nil}}}}
	addTwoNumbers(&l1, &l2)
}

初步自己解题

go
type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var cur1 *ListNode = l1
	var cur2 *ListNode = l2
	var slice1 []string
	var slice2 []string

	// 链表转数组
	for cur1 != nil {
		slice1 = append(slice1, strconv.Itoa(cur1.Val))
		cur1 = cur1.Next
	}

	for cur2 != nil {
		slice2 = append(slice2, strconv.Itoa(cur2.Val))
		cur2 = cur2.Next
	}

	// 反转
	for i := 0; i < len(slice1)/2; i++ {
		temp := slice1[i]
		slice1[i] = slice1[len(slice1)-i-1]
		slice1[len(slice1)-i-1] = temp
	}
	for i := 0; i < len(slice2)/2; i++ {
		temp := slice2[i]
		slice2[i] = slice2[len(slice2)-i-1]
		slice2[len(slice2)-i-1] = temp
	}

	// 数组转字符串
	str1 := strings.Join(slice1, "")
	str2 := strings.Join(slice2, "")

	// 相加计算
	num1, _ := strconv.Atoi(str1)
	num2, _ := strconv.Atoi(str2)
	num := num1 + num2

	// 切割
	numArr := strings.Split(strconv.Itoa(num), "")

	// 反转数组
	var reversalArr []string
	for i := 0; i < len(numArr); i++ {
		reversalArr = append(reversalArr, numArr[len(numArr)-i-1])
	}

	// 反转创建链表
	var returnListNode = new(ListNode)
	var cur = returnListNode
	for i := 0; i < len(reversalArr); i++ {
		// n, _ := strconv.Atoi(numArr[len(numArr)-i])
		n, _ := strconv.Atoi(reversalArr[i])

		// returnListNode.Val = n  //这样创建就会报错 自己写的不对 panic: runtime error: invalid memory address or nil pointer dereference
		// returnListNode = returnListNode.Next

		returnListNode.Next = &ListNode{Val: n}
		returnListNode = returnListNode.Next
	}

	return cur.Next

}

自己用的很笨的方法 不过是我第一时间想出来的 还是没有链表思想

失败的原因可能是数字超过 go int 类型的最大值了 (我换了 uint64 但是 func strconv.Atoi(s string) (int, error)这个函数返回值是 int 类型 所以不了了之了)

别人的题解

思路：

不断遍历两个链表，然后讲两个节点的数值相加。

注意：相加的总和（下面代码中的 totalValue）可能会产生超出 10 的范围，超出 10 的范围需要将超出的数值（下面代码中的 preValue）保留到下一个节点使用。

时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1)的时间。

空间复杂度：O(1)。注意返回值不计入空间复杂度。

go
type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	resultNode := new(ListNode)
	tempNode := resultNode
	preValue := 0

	// 两个链表不为空, 一直遍历
	for l1 != nil || l2 != nil {
		val1, val2, currentValue := 0, 0, 0

		if l1 != nil {
			val1 = l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			val2 = l2.Val
			l2 = l2.Next
		}

		// 取得当前总和
		totalValue := val1 + val2 + preValue
		// 当前"个位"与"进位"值
		currentValue, preValue = totalValue%10, totalValue/10

		tempNode.Next = &ListNode{Val: currentValue}
		tempNode = tempNode.Next
	}

	// 产生进位的特殊情况判断
	if preValue > 0 {
		tempNode.Next = &ListNode{Val: preValue}
	}

	return resultNode.Next
}