链表相加(二)

package main
import . "nc_tools"

// import "fmt"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
*/
func addInList( head1 *ListNode ,  head2 *ListNode ) *ListNode {
    p1,p2:=reverse(head1),reverse(head2)
    var ans,tail *ListNode
    carry:=0
    for p1!=nil||p2!=nil{
        val:=carry
        if p1!=nil{
            val+=p1.Val
            p1=p1.Next
        }
        if p2!=nil{
            val+=p2.Val
            p2=p2.Next
        }
        carry=val/10
        val%=10
        node:=&ListNode{Val: val}
        if ans==nil{
            ans=node
            tail=ans
        }else{
            tail.Next=node
            tail=tail.Next
        }
    }
    if carry!=0{
        tail.Next=&ListNode{Val: carry}
    }
    return reverse(ans)
}

func reverse(head *ListNode)*ListNode{
    p,q:=head,head.Next
    for q!=nil{
        tmp:=q.Next
        q.Next=p
        p=q
        q=tmp
    }
    head.Next=nil
    return p
}

func addInList( head1 *ListNode ,  head2 *ListNode ) *ListNode {
    // write code here
    head1 = recover(head1)
    head2 = recover(head2)
    var res *ListNode
    var more int
    for head1 != nil || head2 != nil || more > 0 {
        var sum int
        if head1 != nil {
            sum += head1.Val
            head1 = head1.Next
        }
        if head2 != nil {
            sum += head2.Val
            head2 = head2.Next
        }
        res = &ListNode{
            Val: (sum+more)%10,
            Next: res,
        }
        more = (sum+more)/10
    }
    return res
}

func  recover(head *ListNode) *ListNode {
    var pre *ListNode
    var next *ListNode
    for head != nil {
        next = head.Next
        head.Next = pre
        pre = head
        head = next
    }
    return pre
}

func addInList(head1 *ListNode, head2 *ListNode) *ListNode {
	head1 = reversal(head1)
	head2 = reversal(head2)

	result := new(ListNode)
	tmp := result

	// 这题和 string 加法一样的操作
	add := 0 // 进位
	cur := 0 // 当前位的值
	for head1 != nil || head2 != nil || add != 0 {
		if head1 == nil && head2 != nil {
			cur = head2.Val + add
		} else if head1 != nil && head2 == nil {
			cur = head1.Val + add
		} else if head1 == nil && head2 == nil {
			cur = add
		} else {
			cur = head2.Val + head1.Val + add
		}

		if cur > 9 {
			add = cur / 10
			cur -= 10
		} else {
			add = 0
		}

		tmp.Next = &ListNode{Val: cur, Next: nil}
		tmp = tmp.Next

		if head1 != nil {
			head1 = head1.Next
		}

		if head2 != nil {
			head2 = head2.Next
		}
	}

  // 最后别忘了反转回来
	return reversal(result.Next)
}

// 反转链表
func reversal(head *ListNode) *ListNode {
	pre := head
	var cur *ListNode = nil

	for pre != nil {
		tmp := pre.Next
		pre.Next = cur
		cur = pre
		pre = tmp
	}

	return cur
}

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)
    stack2 := 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
    }
    
    var tmp = 0
    var head *ListNode
    for len(stack1) != 0 || len(stack2) != 0 || tmp != 0{
        var x, y = 0, 0
        if len(stack1) != 0 {
            x = stack1[len(stack1)-1]
            stack1 = stack1[:len(stack1)-1]
        }
        if len(stack2) != 0 {
            y = stack2[len(stack2)-1]
            stack2 = stack2[:len(stack2)-1]
        }
        sum := x + y + tmp
        tmp = sum/10
        
        newNode := &ListNode{
            Val: sum%10,
            Next : head,
        }
        head = newNode
    }
    return head
}