leetCode-2-Add-Two-Numbers 扩展

[cocoklp]

/*
链表反序存储时，是不是可以使用堆栈？
*/

type stack []int

func (s *stack) push(item int) {
	(*s) = append((*s), item)
}

func (s *stack) pop() int {
	item := (*s)[len(*s)-1]
	(*s) = (*s)[:len(*s)-1]
	return item
}

func (s stack) depth() int {
	return len(s)
}

func addTwoReverseNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	sumStack := make(stack, 0)
	carryStack := make(stack, 0)
	carry := 0
	for l1 != nil || l2 != nil {
		l1val := 0
		l2val := 0
		if l1 != nil {
			l1val = l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			l2val = l2.Val
			l2 = l2.Next
		}
		sum := l1val + l2val
		carry = sum / 10
		sumStack.push(sum % 10)
		carryStack.push(carry)
	}
	sumList := new(ListNode)

	isFirst := true
	carry = 0
	for sumStack.depth() != 0 || carryStack.depth() != 0 || carry != 0 {
		curSum := 0
		curCarry := 0
		curNode := new(ListNode)
		if sumStack.depth() != 0 {
			curSum = sumStack.pop()
		}
		if !isFirst && carryStack.depth() != 0 {
			curCarry = carryStack.pop()
		}
		isFirst = false
		curVal := (curSum + curCarry + carry)
		carry = curVal / 10
		curNode.Val = curVal % 10
		curNode.Next = sumList.Next
		sumList.Next = curNode
	}
	return sumList.Next
}

[wind-liang]

是一种思路，但是用栈的话会消耗额外空间