leetcode 两数相加

题目描述：

https://leetcode-cn.com/problems/add-two-numbers-ii/

解

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 获取两个链表长度
    if l1 == nil || l2 == nil {
        return nil
    }
    var (
        ret = l1
    )
    l1Len := GetListLen(l1)
    l2Len := GetListLen(l2)
    if l1Len > l2Len {
        ret = l1
    }
    if l1Len < l2Len {
        ret = l2
    }
    if n := insertNumberV2(l1, l2, ret, l1Len, l2Len); n != 0 {
        return &ListNode{
            Val:  n,
            Next: ret,
        }
    }
    return ret
}

func GetListLen(l *ListNode) int {
    var n = 1
    for {
        if l.Next != nil {
            n++
            l = l.Next
        } else {
            return n
        }
    }
}
func insertNumberV2(l1, l2, l3 *ListNode, l1Len, l2Len int) int {
    if l1.Next == nil && l2.Next == nil {
        var ret = l1.Val + l2.Val
        l3.Val = ret % 10
        return ret / 10
    }
    if l1Len > l2Len {
        ret := insertNumberV2(l1.Next, l2, l3.Next, l1Len-1, l2Len)
        if ret != 0 {
            total := l1.Val + ret
            l3.Val = total % 10
            return total / 10
        }
        return 0
    }
    if l1Len < l2Len {
        ret := insertNumberV2(l1, l2.Next, l3.Next, l1Len, l2Len-1)
        if ret != 0 {
            total := l2.Val + ret
            l3.Val = total % 10
            return total / 10
        }
        return 0
    }
    // 相加
    ret := insertNumberV2(l1.Next, l2.Next, l3.Next, l1Len-1, l2Len-1)
    total := l1.Val + l2.Val + ret
    l3.Val = total % 10
    return total / 10
}

---

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 获取两个链表长度
    if l1 == nil || l2 == nil {
        return nil
    }
    var (
        ret = l1
    )
    l1Len := GetListLen(l1)
    l2Len := GetListLen(l2)
    if l1Len > l2Len {
        ret = l1
    }
    if l1Len < l2Len {
        ret = l2
    }
    if n := insertNumberV2(l1, l2, ret, l1Len, l2Len); n != 0 {
        return &ListNode{
            Val:  n,
            Next: ret,
        }
    }
    return ret
}

func GetListLen(l *ListNode) int {
    var n = 1
    for {
        if l.Next != nil {
            n++
            l = l.Next
        } else {
            return n
        }
    }
}
func insertNumberV2(l1, l2, l3 *ListNode, l1Len, l2Len int) int {
    if l1.Next == nil && l2.Next == nil {
        var ret = l1.Val + l2.Val
        l3.Val = ret % 10
        return ret / 10
    }
    if l1Len > l2Len {
        ret := insertNumberV2(l1.Next, l2, l3.Next, l1Len-1, l2Len)
        if ret != 0 {
            total := l1.Val + ret
            l3.Val = total % 10
            return total / 10
        }
        return 0
    }
    if l1Len < l2Len {
        ret := insertNumberV2(l1, l2.Next, l3.Next, l1Len, l2Len-1)
        if ret != 0 {
            total := l2.Val + ret
            l3.Val = total % 10
            return total / 10
        }
        return 0
    }
    // 相加
    ret := insertNumberV2(l1.Next, l2.Next, l3.Next, l1Len-1, l2Len-1)
    total := l1.Val + l2.Val + ret
    l3.Val = total % 10
    return total / 10
}

以上，第一项使用递归·而第二项使用栈

递归
栈

引用

https://leetcode-cn.com/problems/add-two-numbers-ii/submissions/