算法 链表相加问题

链表相加问题

假定目前存在两个整数链表,并且约定每个元素的取值范围都是[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
}