题解 | #两个链表生成相加链表# go + 三个栈实现

go + 三个栈实现

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
*/
func addInList( head1 *ListNode ,  head2 *ListNode ) *ListNode {
    // write code here
//  使用三个栈实现
    stack1 := make([]int, 0) // 存储链表1的数值
    stack2 := make([]int, 0) // 存储链表2的数值
    stack3 := make([]int, 0) // 存储 相加得到的值

    for head1 != nil {
        stack1 = append(stack1, head1.Val)
        head1 = head1.Next
    }
    for head2 != nil {
        stack2 = append(stack2, head2.Val)
        head2 = head2.Next
    }

    carry := 0
    for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
        m := 0
        if len(stack1) > 0 {
            m = stack1[len(stack1)-1]
            stack1 = stack1[:len(stack1)-1]
        }
        n := 0
        if len(stack2) > 0 {
            n = stack2[len(stack2)-1]
            stack2 = stack2[:len(stack2)-1]
        }

        var v int
        sum := m+n+carry
        v, carry = sum%10, sum/10

        stack3 = append(stack3, v)
    }

//  创建新的链表
    head := &ListNode{}
    node := head
    for i:=len(stack3)-1; i>=0;i-- {
        v := stack3[i]
        node.Next = &ListNode{Val: v}

        node = node.Next
    }

    return head.Next
}