链表求和 golang

链表求和

在编程中，链表是一种常见的数据结构，它由一系列的节点组成，每个节点包含一个值和指向下一个节点的指针。链表求和是一个常见的问题，可以通过遍历链表并累加节点的值来实现。

首先，我们需要定义一个链表的节点结构体：

type ListNode struct {
    Val  int
    Next *ListNode
}

接下来，我们可以编写一个函数，用于计算两个链表的和：

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    curr := dummy
    carry := 0

    for l1 != nil || l2 != nil {
        sum := carry

        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }

        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }

        curr.Next = &ListNode{Val: sum % 10}
        carry = sum / 10
        curr = curr.Next
    }

    if carry > 0 {
        curr.Next = &ListNode{Val: carry}
    }

    return dummy.Next
}

上述代码使用了一个虚拟头节点dummy，以及一个当前节点curr和进位标志carry来将两个链表逐位相加。我们首先初始化dummy和curr为一个空节点，并将carry初始化为0。

然后，我们进入一个循环，只有当l1和l2都为空时才退出。在每次循环中，我们将carry加到当前两个节点值的和上，并更新l1和l2的指针。

接着，我们创建一个新的节点，并将其值设置为当前和的个位数。然后，我们更新carry为当前和的十位数，并将当前节点指向新创建的节点。

最后，如果carry大于0，则说明还有进位，我们需要创建一个新的节点，并将其设置为carry。最后返回dummy的下一个节点即可。

接下来，我们可以编写一些测试代码来验证我们的求和函数：

func main() {
    l1 := &ListNode{Val: 2}
    l1.Next = &ListNode{Val: 4}
    l1.Next.Next = &ListNode{Val: 3}

    l2 := &ListNode{Val: 5}
    l2.Next = &ListNode{Val: 6}
    l2.Next.Next = &ListNode{Val: 4}

    result := addTwoNumbers(l1, l2)

    for result != nil {
        fmt.Print(result.Val)
        result = result.Next
    }
}

输出结果为524，这是因为2+5=7，4+6=10（进位1），以及3+4=7。

通过这个例子，我们可以看到链表求和是一个相对简单的问题，但是需要注意处理进位和边界条件。这种方法的时间复杂度为O(max(m, n))，其中m和n分别表示两个链表的长度。空间复杂度为O(max(m, n))，主要是由于结果链表的长度。

总结来说，链表求和是一个常见且经典的问题，可以通过遍历链表、进位标志和创建新节点的方法来解决。在实际应用中，链表求和可以用于处理各种数学问题，例如大整数相加、多项式求和等。对于Golang开发者来说，熟悉链表求和的实现方法可以帮助我们更好地处理相关问题。