两数相加 | 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 := 0
    l2Val := 0
    if l1 != nil {
        l1Val = l1.Val
        l1 = l1.Next
    }
    if l2 != nil {
        l2Val = l2.Val
        l2 = l2.Next
    }
    r := &ListNode{Val : (l1Val + l2Val + isPlusOne)}
    if 9 < r.Val {
        r.Val = r.Val % 10
        isPlusOne = 1
    }else{
        isPlusOne = 0
    }
    r.Next = calc(l1 , l2 , isPlusOne)
    return r

}

官方解答

func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {
    var tail *ListNode
    carry := 0
    for l1 != nil || l2 != nil {
        n1, n2 := 0, 0
        if l1 != nil {
            n1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            n2 = l2.Val
            l2 = l2.Next
        }
        sum := n1 + n2 + carry
        sum, carry = sum%10, sum/10
        if 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 := 0
    cur := dummy
    for l1 != nil || l2 != nil || carry != 0 {
        s := carry
        if l1 != nil {
            s += l1.Val
        }
        if l2 != nil {
            s += l2.Val
        }
        carry = s / 10
        cur.Next = &ListNode{s % 10, nil}
        cur = cur.Next
        if l1 != nil {
            l1 = l1.Next
        }
        if l2 != nil {
            l2 = l2.Next
        }
    }
    return dummy.Next
}

英语文章出处