445. Add Two Numbers II #
Problem #
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
Problem Summary #
This problem is a variant of Problem 2. In Problem 2, the two numbers are arranged in reverse order from the ones place to the higher digits, so adding them only requires traversing from head to tail and carrying continuously. This problem explicitly requires that the linked lists cannot be reversed. The 2 numbers are arranged from high digits to low digits, so the carries come in reverse.
Solution Approach #
The idea is not difficult either. For addition, you only need to add the shorter linked list to the longer linked list in order, and finally check whether there is a carry in the highest digit; if there is a carry, advance one more digit. The addition process can use recursion.
Code #
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
}
中文