原题

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 contain a single digit.

这些数字以相反的顺序存储,它们的每个节点包含一个数字。

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

将这两个数字相加,然后以链表的形式返回。

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

你可以假设这两个数字不包含任何前导零,除了数字0本身。

题目大意

2 个逆序的链表,要求从低位开始相加,得出结果也逆序输出,返回值是逆序结果链表的头结点。

栗子:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

结题思路

需要注意的是各种进位问题。

极端情况,例如:

Input: (9 -> 9 -> 9 -> 9 -> 9) + (1 -> )
Output: 0 -> 0 -> 0 -> 0 -> 0 -> 1

为了处理方法统一,可以先建立一个虚拟头结点,这个虚拟头结点的 Next 指向真正的 head,这样 head 不需要单独处理,直接 while 循环即可。另外判断循环终止的条件不用是 p.Next != nil,这样最后一位还需要额外计算,循环终止条件应该是 p != nil。

代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    //准备一个返回的链表
    head := &ListNode{Val: 0}
    //准备变量
    n1, n2, carry, current := 0, 0, 0, head
    //链表不为空或者carry不等于0都可以进入循环
    for l1 != nil || l2 != nil || carry != 0 {
        //链表1是空则n1 为0 ,否者n1存储链表指向的值,l1链表后移 
        if l1 == nil {
            n1 = 0
        } else {
            n1 = l1.Val
            l1 = l1.Next
        }
        //链表1是空则n2为0 ,否者n2存储链表指向的值,l2链表后移 
        if l2 == nil {
            n2 = 0
        } else {
            n2 = l2.Val
            l2 = l2.Next
        }
        //创建链表的下一个节点,加入链表
        current.Next = &ListNode{Val: (n1 + n2 + carry) % 10}
        current = current.Next
        carry = (n1 + n2 + carry) / 10
    }
    //返回链表
    return head.Next
}

本文转自https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0002.Add-Two-Numbers/

最后修改:2021 年 06 月 29 日 10 : 46 AM
如果觉得我的文章对你有用,请随意赞赏