2018-08-26

题目如下:
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

直接能够想到的就是把链表中的数组组成一个整数然后相加,但是对于较长的链表而言,整数范围是不够滴(leetcode上最后的例子数字已经超过了64位所能代表的最大整数,浮点数没有具体计算过),而且时间复杂度,应该是O(2(m+n)),取数一次操作,赋值又一次操作.所以这里考虑将每一个节点的值相加,然后赋值给新的链表,时间复杂度为O(max(m,n)),并且不会出现数值过大无法计算的情况.

代码如下

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {

    p1 := l1
    p2 := l2
    p1Next := p1
    p2Next := p2
    p3 := &ListNode{}
    p3Next := p3
    CF := 0

    for {

        if p1Next != nil || p2Next != nil || CF != 0{

            v1 :=0
            if(p1Next != nil){
                 v1= p1Next.Val
            }
            v2 := 0
            if(p2Next != nil){
                v2= p2Next.Val
            }

            val := v1 + v2 + CF
            if val >= 10 {
                p3Next.Val = val - 10
                CF = 1
            } else {
                p3Next.Val = val
                CF = 0
            }

            if p1Next != nil {
                p1Next = p1Next.Next
            }
            if p2Next != nil {
                p2Next = p2Next.Next
            }

            if(p1Next != nil || p2Next!= nil || CF!=0){
                p3Next.Next = &ListNode{}
                p3Next = p3Next.Next
            }
        }else{
            break
        }
    }
    return p3
}