How to use golang language to implement the linked list summation algorithm

Summing linked lists is a common algorithm problem. Its basic idea is to add the digits in two linked lists to obtain a new linked list representing their sum. This sum may involve carry Digits increase.

This article will introduce how to use golang language to implement the linked list summation algorithm.

First, we need to define a structure of a linked list node, which contains two fields: val represents the value of the node, and next represents the pointer to the next node.

type ListNode struct {
    Val  int
    Next *ListNode
}

Next, we can define a function AddTwoNumbers, which receives two linked lists l1 and l2, and returns a new linked list composed of their sum.

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    carry := 0  // 进位值
    dummy := &ListNode{Val: 0, Next: nil}
    curr := dummy  // 当前节点

    for l1 != nil || l2 != nil {
        // 如果两个链表长度不相等，在较短的链表上添加一个0节点，使两个链表长度相等
        if l1 == nil {
            l1 = &ListNode{Val: 0, Next: nil}
        }
        if l2 == nil {
            l2 = &ListNode{Val: 0, Next: nil}
        }

        sum := l1.Val + l2.Val + carry
        carry = sum / 10  // 更新进位值
        curr.Next = &ListNode{Val: sum % 10, Next: nil}
        curr = curr.Next

        l1 = l1.Next
        l2 = l2.Next
    }

    // 最后如果还有进位，添加一个进位节点
    if carry > 0 {
        curr.Next = &ListNode{Val: carry, Next: nil}
    }

    return dummy.Next
}

In this function, we use the carry variable to represent the carry value, and the initial value is 0. We define a dummy node dummy, which points to the head of the new linked list, and a pointer curr, which points to the current node of the new linked list, with the initial value pointing to the dummy node. Then we use a for loop to traverse the two linked lists. At this time we need to note that if the lengths of the two linked lists are not equal, we need to add a 0 node to the shorter linked list to make the two linked lists equal in length. Next, we add the nodes at the same position in the linked list, and add the carry value to the value of the current node to get a new sum value, whose tens digit may be carried to the next addition. Therefore, we need to update the value of carry. At the same time, we use the single digit of sum as the value of the new node, and point the curr pointer to this newly created node. Finally, we let the curr pointer point to the next node of the new linked list, and then move the pointers of l1 and l2 to their next nodes. Repeat this process until both linked lists have been traversed. Finally, if there is a carry, add a carry node. Finally, dummy.Next is returned, which represents the head node of the new linked list.

Next we can define a test function to test the AddTwoNumbers function.

func TestAddTwoNumbers(t *testing.T) {
    l1 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3, Next: nil}}}
    l2 := &ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4, Next: nil}}}
    l3 := AddTwoNumbers(l1, l2)
    if l3.Val != 7 || l3.Next.Val != 0 || l3.Next.Next.Val != 8 || l3.Next.Next.Next != nil {
        t.Errorf("AddTwoNumbers(%v, %v) = %v, want %v", l1, l2, l3, &ListNode{Val: 7, Next: &ListNode{Val: 0, Next: &ListNode{Val: 8, Next: nil}}})
    }
}

In this test function, we create two linked lists l1 and l2, which represent 342 and 465 respectively. We call the AddTwoNumbers function, calculate their sum, and get the new linked list l3, whose value should be 708. We use the if statement to check the value of l3. If it does not meet expectations, we use the t.Errorf method to record the error message.

Save the above code in the sumLinkedList.go file, run the test function, and you will get the output result:

$ go test -v
=== RUN   TestAddTwoNumbers
--- PASS: TestAddTwoNumbers (0.00s)
PASS
ok      sumLinkedList  0.360s

Through the test function, we can confirm that the implementation of the linked list summation algorithm is correct .

This article introduces in detail how to use golang to implement the linked list summation algorithm, including defining the structure of the linked list nodes and the specific steps to implement the AddTwoNumbers function. This algorithm is a question that is often encountered in interviews. With its own implementation, you can prepare better and also help deepen your understanding of linked lists and pointers.

The above is the detailed content of How to use golang language to implement the linked list summation algorithm. For more information, please follow other related articles on the PHP Chinese website!