算法 链表相加问题

链表相加问题

假定目前存在两个整数链表，并且约定每个元素的取值范围都是[0,9]。 每个链表用来表示一个数字的反序，例如[4,2,5]表示524，[9，6，2，4，5]表示54269. 现在要求对跟定的两个数组进行相加运算，并且输出相加之和的链表。

例如:

l1 = [4，2，5]  
l2 = [3，8，3]

l1+l2=[8，0，8]

解决方案 一 通过数字相加

既然每个链表表示的是一个数字的逆序，那么可以通过将链表转换成数字，然后再通过数字进行相加，将结果再转回数字的方式进行求解。 也就是下面的过程：

ListNode 1 ---> Number
            +          =      Number ---------> ListNode
   ListNode 2 ---> Number

func convertListNodetoInt(l *ListNode) (result int) {  
    level := 0

    for {
        weight := 1
        for i := 0; i < level; i++ {
            weight *= 10
        }

        result += l.Val * weight

        if l.Next != nil {
            l = l.Next
            level++
        } else {
            return result
        }
    }
}

func convertIntToListNode(result int) *ListNode {

    if result == 0 {
        return &ListNode{
            Val:  result,
            Next: nil,
        }
    }

    level := 1

    weight := 1
    for (result/weight != 0) {
        weight *= 10
        level++
    }

    //当商是0的时候，才是真正的层级。但上面的逻辑多添加了一层。所以回退一层
    level --
    weight /= 10

    if level == 1 {
        return &ListNode{
            Val:  result,
            Next: nil,
        }
    }

    weight = 10
    var ls []*ListNode

    for i := 1; i <= level; i++ {
        ls = append(ls, &ListNode{
            Val:  result % weight,
            Next: nil,
        })

        //  保留商数
        result /= weight
    }

    for i := 0; i < len(ls)-1; i++ {
        ls[i].Next = ls[i+1]
    }

    return ls[0]
}

这个方案有个最大的弊端，可支持的数字范围是受限的。 即便使用int64,也是有上限的。 但链表理论上是无限扩展的，所以这个方案只能解决int64以下的数据集。

方案二 链表直接相加

第二个方案是模拟人类计算的过程。 例如我们在计算325+456时，是按照下面的过程进行计算的:

3 2 5
                           + 4 5 6
                           -------
                           = 7 8 1

首先按低位向高位的循序进行按位相加，如果结果对10求商大于1，则向前进一位，否则不进位。并将结果对10取模之后的数字作为此位的最终结果。 逐位处理，直到某一位为空时，最后处理进位然后停止。

所以按照这个逻辑，依次对两个链表中的元素进行求和运算，将合数对10求商。如果计算到某个链表为空时，则表明一个数字计算完毕，此时将另外一个链表的元素与进位相加，作为最终结果。

代码如下:

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

    result := &ListNode{}
    curr := result
    carry := 0
    for (l1 != nil || l2 != nil) {
        _x := 0
        if l1 == nil {
            _x += l2.Val
        } else if l2 == nil {
            _x += l1.Val
        } else {
            _x += l1.Val + l2.Val
        }

        _x += carry

        carry = _x / 10

        curr.Next = &ListNode{
            Val: _x % 10,
        }
        curr = curr.Next

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

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

    if carry > 0 {
        curr.Next = &ListNode{
            Val:  carry,
            Next: nil,
        }
    }
    return result.Next
}