445. Add Two Numbers II #
题目 #
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
题目大意 #
这道题是第 2 题的变种题，第 2 题中的 2 个数是从个位逆序排到高位，这样相加只用从头交到尾，进位一直进位即可。这道题目中强制要求不能把链表逆序。2 个数字是从高位排到低位的，这样进位是倒着来的。
解题思路 #
思路也不难，加法只用把短的链表依次加到长的链表上面来就可以了，最终判断一下最高位有没有进位，有进位再往前进一位。加法的过程可以用到递归。
代码 #
package leetcode
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
package leetcode
import (
"github.com/halfrost/leetcode-go/structures"
)
// ListNode define
type ListNode = structures.ListNode
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers445(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
l1Length := getLength(l1)
l2Length := getLength(l2)
newHeader := &ListNode{Val: 1, Next: nil}
if l1Length < l2Length {
newHeader.Next = addNode(l2, l1, l2Length-l1Length)
} else {
newHeader.Next = addNode(l1, l2, l1Length-l2Length)
}
if newHeader.Next.Val > 9 {
newHeader.Next.Val = newHeader.Next.Val % 10
return newHeader
}
return newHeader.Next
}
func addNode(l1 *ListNode, l2 *ListNode, offset int) *ListNode {
if l1 == nil {
return nil
}
var (
res, node *ListNode
)
if offset == 0 {
res = &ListNode{Val: l1.Val + l2.Val, Next: nil}
node = addNode(l1.Next, l2.Next, 0)
} else {
res = &ListNode{Val: l1.Val, Next: nil}
node = addNode(l1.Next, l2, offset-1)
}
if node != nil && node.Val > 9 {
res.Val++
node.Val = node.Val % 10
}
res.Next = node
return res
}
func getLength(l *ListNode) int {
count := 0
cur := l
for cur != nil {
count++
cur = cur.Next
}
return count
}
func addTwoNumbers1(l1 *ListNode, l2 *ListNode) *ListNode {
reservedL1 := reverseList(l1)
reservedL2 := reverseList(l2)
dummyHead := &ListNode{}
head := dummyHead
carry := 0
for reservedL1 != nil || reservedL2 != nil || carry > 0 {
val := carry
if reservedL1 != nil {
val = reservedL1.Val + val
reservedL1 = reservedL1.Next
}
if reservedL2 != nil {
val = reservedL2.Val + val
reservedL2 = reservedL2.Next
}
carry = val / 10
head.Next = &ListNode{Val: val % 10}
head = head.Next
}
return reverseList(dummyHead.Next)
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
tmp := head.Next
head.Next = prev
prev = head
head = tmp
}
return prev
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
stack1 := pushStack(l1)
stack2 := pushStack(l2)
dummyHead := &ListNode{}
head := dummyHead
carry := 0
for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
val := carry
if len(stack1) > 0 {
val = val + stack1[len(stack1)-1]
stack1 = stack1[:len(stack1)-1]
}
if len(stack2) > 0 {
val = val + stack2[len(stack2)-1]
stack2 = stack2[:len(stack2)-1]
}
carry = val / 10
tmp := head.Next
head.Next = &ListNode{Val: val % 10, Next: tmp}
}
return dummyHead.Next
}
func pushStack(l *ListNode) []int {
var stack []int
for l != nil {
stack = append(stack, l.Val)
l = l.Next
}
return stack
}