leetcode挑战: 两数相加

<< 更多leetcode题目

题目链接

https://leetcode.cn/problems/add-two-numbers/

难度

中等

C++解决方案

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int c = 0;
        ListNode* l = nullptr;
        ListNode** p = &l;
        while (l1 || l2 || c)
        {
            // 求和，需要考虑进位
            int v = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + c;
            // 计算是否产生进位
            c = v / 10;
            // 将node添加到新链表
            *p = new ListNode(v % 10);
            p = &(*p)->next;
            l1 = l1 ? l1->next : l1;
            l2 = l2 ? l2->next : l2;
        }

        return l;
    }
};

Python解决方案

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        if l1 is None or l2 is None:
            return None

        c = 0
        l3 = None
        while l1 is not None or l2 is not None or c != 0:
            # 求和，需要考虑进位
            v1 = 0 if l1 is None else l1.val
            v2 = 0 if l2 is None else l2.val
            v = v1 + v2 + c
            # 计算是否产生进位
            c = v // 10
            # 将node添加到新链表
            node = ListNode(v % 10)
            if l3 is None:
                l3 = node
                prev = l3
            else:
                prev.next = node
                prev = node
            l1 = l1 if l1 is None else l1.next
            l2 = l2 if l2 is None else l2.next

        return l3

解题思路

因为输入链表是逆序的，即低位数字在前，高位数字在后，所以直接遍历链表累加即可。唯一需注意的就是要考虑到两数相加可能会产生进位。

总结

这道题目踩了一个大坑！
易水最初拿到这个题目时，第一次尝试，是把输入的链表转换为 int 类型，求和后再转换为链表输出。但第一次提交时 leetcode 返回了Runtime Error！
原因是漏看了限制条件，这个链表长度最长为100，也就是说它可表示一个最长100位的整数！这远远超过了 int 类型可表示的范围(是否也超出了 uint64 所能表示的范围？)，因此产生了溢出。 这种实现方式还存在另外一个问题，那就是当链表长度增加时，执行时间可能也会非常长，因为它需要做乘法操作！
所以，以后在分析题目时，一定要认真阅读限制条件，当限制条件不同时，可采取的解决办法也会随之变化。
Python 版本只是 C++ 版本的一个简单翻译。在实现中遇到两个问题，一是不了解 Optional 的用法，查了一下， Optional[x] 实际上就相当于 Union[x, None]；二是不知道在 Python 中如何表示链表，后来仔细想了一下，Python 和 Java 类似，它的变量名就等同于 C++ 中的指针，所以链表的头指针实际上就是变量 l3。