算法: 核心问题是进位的操作:
1)不要忘记进位之后的哪一个1;
2)不要忘记所有位都操作完了之后,最后的哪一个进位1
变形题目的话,需要想办法转换成 题目1这种原子操作的题目。
题目 1: 两数相加:
https://leetcode-cn.com/problems/add-two-numbers/
代码:
// 算法: 核心问题是:进位的操作,
// 1)不要忘记进位之后的哪一个1;
// 2)不要忘记所有位都操作完了之后,最后的哪一个进位1
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
h := new(ListNode)
pre,res := h,h
m, n := l1, l2
for m != nil && n != nil {
tmp := new(ListNode)
sum := m.Val + n.Val + res.Val
if sum >= 10 {
tmp.Val = 1
}
pre = res
res.Val = sum % 10
res.Next = tmp
res = res.Next
m = m.Next
n = n.Next
}
for m != nil {
tmp := new(ListNode)
s := m.Val + res.Val
if s >= 10 {
tmp.Val = 1
}
pre = res
res.Val = s % 10
res.Next = tmp
res = res.Next
m = m.Next
}
for n != nil {
tmp := new(ListNode)
s := n.Val + res.Val
if s >= 10 {
tmp.Val = 1
}
pre = res
res.Val = s % 10
res.Next = tmp
res = res.Next
n = n.Next
}
if res.Val == 0 {
pre.Next = nil
}
return h
}
运行结果:
题目 2: 两数之和:
https://leetcode-cn.com/problems/sum-lists-lcci/
代码实现:
// 算法:实现方式与题目1一致,
// 本题代码相当于对题目1的解法做了一个代码层面的优化
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
res := new(ListNode)
n := res
r := 0
// 相同位的计算
for l1 != nil && l2 != nil {
s:= r + l1.Val + l2.Val
if s >= 10 {
r = 1
} else {
r = 0
}
tmp := ListNode{Val:s%10}
res.Next = &tmp
l1 = l1.Next
l2 = l2.Next
res = res.Next
}
// 位数不同的两个数的,高位数计算
var result *ListNode
if l1 != nil {
result = l1
} else if l2 != nil {
result = l2
}
for result != nil {
s:= r + result.Val
if s >= 10 {
r = 1
} else {
r = 0
}
tmp := ListNode{Val:s%10}
res.Next = &tmp
result = result.Next
res = res.Next
}
// 最后的进位
if r != 0 {
tmp := ListNode{Val:r}
res.Next = &tmp
}
return n.Next
}
执行结果:
题目 3 :两数相加
https://leetcode-cn.com/problems/add-two-numbers-ii/
// 算法:
// 核心点在于,链表的低位是数字的高位,只要能够将链表的高低位交换,就变成题目1.
// 采用数组顺序性去实现高低位的反转,从数组末尾遍历就可以了。
// 剩下的思路与题目1一致。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
var a,b,c []*ListNode
for l1 != nil {
a = append(a,l1)
l1 = l1.Next
}
for l2 != nil {
b = append(b,l2)
l2 = l2.Next
}
c = Sum(a,b)
res := new(ListNode)
n := res
for i := len(c)-1;i>=0;i-- {
res.Next = c[i]
res = res.Next
}
return n.Next
}
func Sum(a,b []*ListNode) (c []*ListNode){
r := 0
i, j := len(a)-1,len(b)-1
for i>=0 && j >=0 {
s := r + a[i].Val+b[j].Val
tmp := new(ListNode)
tmp.Val = s%10
c = append(c,tmp)
if s >= 10 {
r = 1
} else {
r = 0
}
i--
j--
}
for i >= 0{
s := r + a[i].Val
tmp := new(ListNode)
tmp.Val = s%10
if s >= 10 {
r = 1
} else {
r = 0
}
c = append(c,tmp)
i--
}
for j >= 0{
s := r + b[j].Val
tmp := new(ListNode)
tmp.Val = s%10
if s >= 10 {
r = 1
} else {
r = 0
}
c = append(c,tmp)
j--
}
if r != 0 {
c = append(c,&ListNode{Val:r})
}
return c
}
运行结果: