leetcode系列(双语)002——GO两数相加

本文主要是介绍leetcode系列(双语)002——GO两数相加，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

两数相加 | Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit.

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

Add the two numbers and return the sum as a linked list.

请你将两个数相加，并以相同形式返回一个表示和的链表。

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

个人解答

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {return calc(l1 , l2 , 0)
}func calc(l1 *ListNode, l2 *ListNode, isPlusOne int) *ListNode{if l1 == nil && l2 == nil && isPlusOne == 0 {return nil}l1Val := 0l2Val := 0if l1 != nil {l1Val = l1.Vall1 = l1.Next}if l2 != nil {l2Val = l2.Vall2 = l2.Next}r := &ListNode{Val : (l1Val + l2Val + isPlusOne)}if 9 < r.Val {r.Val = r.Val % 10isPlusOne = 1}else{isPlusOne = 0}r.Next = calc(l1 , l2 , isPlusOne)return r}

官方解答

func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {var tail *ListNodecarry := 0for l1 != nil || l2 != nil {n1, n2 := 0, 0if l1 != nil {n1 = l1.Vall1 = l1.Next}if l2 != nil {n2 = l2.Vall2 = l2.Next}sum := n1 + n2 + carrysum, carry = sum%10, sum/10if head == nil {head = &ListNode{Val: sum}tail = head} else {tail.Next = &ListNode{Val: sum}tail = tail.Next}}if carry > 0 {tail.Next = &ListNode{Val: carry}}return
}

扩展

Algorithm

Create a new LinkedList, and then push the input two linked lists from the beginning to the back, add every two, and add a new node to the back of the new linked list.

In order to prevent the two input linked lists from being empty at the same time, we create a dummy node, and add the new nodes generated by the addition of the two nodes to the dummy node in order.

Since the dummy node itself cannot be changed, a pointer is used cur to point to the last node of the new linked list. Ok, you can start to add the two linked lists.

This problem is good because the lowest bit is at the beginning of the linked list, so you can directly add them in order from low to high while traversing the linked list. The condition of the while loop, as long as one of the two linked lists is not an empty row, since the linked list may be empty, when taking the current node value, judge first, if it is empty then value is 0, otherwise take the node value.

Then add the two node values, and add carry. Then update carry, directly sum/10, and then create a new node with sum%10 as the value, connect it to the back of cur, and then move cur to the next node.

Then update the two nodes, if they exist, point to the next location. After the while loop exits, the highest carry issue needs to be dealt with specially. If carry is 1, then another node with value 1 is created.

 func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {dummy := &ListNode{}carry := 0cur := dummyfor l1 != nil || l2 != nil || carry != 0 {s := carryif l1 != nil {s += l1.Val}if l2 != nil {s += l2.Val}carry = s / 10cur.Next = &ListNode{s % 10, nil}cur = cur.Nextif l1 != nil {l1 = l1.Next}if l2 != nil {l2 = l2.Next}}return dummy.Next
}

英语文章出处

这篇关于leetcode系列(双语)002——GO两数相加的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---