【题目4】Add two numbers(LeetCode)

问题描述

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.

Example

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

问题分析

1. 思路

本题考察链表的操作，利用链表从最低位开始逐位求和，并考虑进位进行求解。

342+456=807的链表结构可视化

2. 算法

本题的题目描述和笔算时的方法类似，从最低位开始求和，也就是链表l1和l2的表头，由于数字范围为0~9，需要考虑进位的问题，且进位只可能是0和1。此外，需要考虑以下特殊情况：

特殊情况	解释
l1=[0,1], l2=[0,1,2]	一个列表比另一个列表长
l1=[], l2=[0,1]	列表为空列表
l1=[9,9], l2=[1]	sum在最后有一个额外的进位，这很容易被忽略

由以上分析可以得到问题的伪代码如下：

将当前节点初始化为返回列表的虚拟表头(dummy)

将进位(carry)初始化为0

将p和q分别初始化为l1和l2的表头
▪ 设x为节点p的值。若p抵达l1的表尾，则为0
▪ 设y为节点q的值。若q抵达l1的表尾，则为0
▪ 设sum = x + y + carry
▪ 更新carry = sum // 10
▪ 创建一个新节点，其值为sum%10，并将其链到当前节点指向的下一个节点
▪ 更新节点到下一个节点，更新p值和q值

检查若carry=1，则在返回列表添加一个值为1的新节点

返回虚拟表头的指向的下一个节点

注：在这里，我们采用dummy head的办法来简化代码。如果不设置dummy head，我们就需要编写额外的条件语句来初始化链表头部的值。

3. 语法细节

定义节点。使用：类+构造方法，构造方法的参数要有节点的数值大小、对下一个节点的指针。
若 l1 表示一个链表，则实质上 l1 表示头节点的指针。

4. 复杂度分析

时间复杂度：O(max(m,n)). 设m和n分别代表l1和l2的长度，本文所用算法迭代的次数最多为m和n中的最大值。
空间复杂度：O(max(m,n)). 新链表的长度最大为max(m,n)+1。

Python代码

# 代码实现
class ListNode:                             # 定义节点，使用：类+构造方法
    def __init__(self, x):
        self.val = x
        self.next = None

def AddTwoNumbers(self, l1, l2):
    dummy = ListNode(0)                     # 将当前节点初始化为返回列表的虚拟表头(dummy)
    carry = 0                               # 将进位(carry)初始化为0
    p = l1; q = l2; curr = dummy            # 将p和q分别初始化为l1和l2的表头
    while(p != None or q != None):
        x = p.val if (p != None) else 0     # 设x为节点p的值。若p抵达l1的表尾，则为0
        y = q.val if (q != None) else 0     # 设y为节点q的值。若q抵达l1的表尾，则为0
        sum = x + y + carry                 # 设sum = x + y + carry
        carry = sum // 10                   # 更新carry = sum // 10
        curr.next = ListNode(sum % 10)      # 创建一个新节点，其值为sum%10，并将其链到当前节点指向的下一个节点
        curr = curr.next                    # 更新节点到下一个节点
        if (p != None): p = p.next          # 更新p值
        if (q != None): q = q.next          # 更新q值
    if carry==1 : curr.next = ListNode(1)   # 检查若carry=1，则在返回列表添加一个值为1的新节点
    return dummy.next                       # 返回虚拟表头的指向的下一个节点

# 实例测试
l1_1 = ListNode(2)                          # 定义链表l1: 2 -> 4 -> 3
l1_2 = ListNode(4)
l1_3 = ListNode(3)
l1_1.next = l1_2
l1_2.next = l1_3

l2_1 = ListNode(5)                          # 定义链表l2: 5 -> 6 -> 4
l2_2 = ListNode(6)
l2_3 = ListNode(4)
l2_1.next = l2_2
l2_2.next = l2_3

l3_1 = AddTwoNumbers(ListNode,l1_1,l2_1)    # 返回结果l3: 7 -> 0 -> 8
while l3_1 != None:
    print(l3_1.val)
    l3_1 = l3_1.next

参考文献

[1] https://leetcode.com/articles/add-two-numbers/
[2] https://www.jianshu.com/p/b98287066140

最后编辑于：2018.03.18 21:18:51