2. Add Two Numbers,单链表两数相加

Last Updated: 2024-06-14 22:49:28 Friday

-- TOC --

从Title上看,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 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.

输入是两个non-negative integers,但是表达方式比较怪异,用的是singly-linked list,并且是按数字的reverse order。要求输出这两个数的sum,使用与输入相同的表达方式。

Constraints:

最大的数可能有100位digit,这是个超大的数字,远远超过了64位unsigned数字可以表达的范围。

>>> len(str(0xFFFFFFFF))          # length of max 32bits integer
10
>>> len(str(0xFFFFFFFFFFFFFFFF))  # length of max 64bits integer
20

这意味着,采用C/C++时,不能使用转int后作加法的思路。其实,reverse order已经简化了问题,个位在singly-linked list的最开始,可以直接开始按位做加法。non-negative也简化了问题,singly-linked list最后不会出现符号。

从左到右按位加

将输入的数字转成int,相加,再转回输出格式,这显然很低效,而且输入的数字可能有100位,C/C++方案肯定不能这么干。因此,自然而然的思路,就是从左到右按位做加法,无它。

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]:
        rtv = l3 = ListNode(0)
        c = 0
        while l1 or l2:
            s = 0
            if l1:
                s += l1.val
                l1 = l1.next
            if l2:
                s += l2.val
                l2 = l2.next
            s += c
            c = s // 10
            l3.next = l3 = ListNode(s%10)

        if c == 1:
            l3.next = ListNode(1)

        return rtv.next

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) {
        ListNode *rtv, *l3;
        rtv = l3 = new ListNode{};

        int s, c{};
        while(l1 || l2){
            s = 0;
            if(l1){
                s += l1->val;
                l1 = l1->next;
            }
            if(l2){
                s += l2->val;
                l2 = l2->next;
            }
            s += c;
            c = s / 10;
            l3 = l3->next = new ListNode{s%10};
        }

        if(c)
            l3 = l3->next = new ListNode{1};

        ListNode *head {rtv};
        rtv = rtv->next;
        delete head;
        return rtv;
    }
};

new失败会raise,因此无需判断返回的指针。但如果真的发生new失败,这里不处理,就会memory leak。C++的Exception Safety分成4个level,这种不处理的情况处于最低level,叫做No exception guarantee — If the function throws an exception, the program may not be in a valid state: resource leaks, memory corruption, or other invariant-destroying errors may have occurred. 最高level是那些被标记为noexcept的接口,保证不会throw。

C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *rtv, *l3;
    rtv = l3 = malloc(sizeof(struct ListNode));

    int s, c=0;
    while(l1 || l2){
        s = 0;
        if(l1){
            s += l1->val;
            l1 = l1->next;
        }
        if(l2){
            s += l2->val;
            l2 = l2->next;
        }
        s += c;
        l3 = l3->next = malloc(sizeof(struct ListNode));
        l3->val = s % 10;
        c = s / 10;
    }

    if(c){
        l3 = l3->next = malloc(sizeof(struct ListNode));
        l3->val = 1;
    }
    l3->next = NULL;

    struct ListNode *head;
    head = rtv;
    rtv = rtv->next;
    free(head);
    return rtv;
}

Python笨算法

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        t = l1
        s1 = ''
        while t:
            s1 += str(t.val)
            t = t.next

        t = l2
        s2 = ''
        while t:
            s2 += str(t.val)
            t = t.next

        s = str(int(s1[::-1])+int(s2[::-1]))[::-1]
        h = t = ListNode(int(s[0]))
        for c in s[1:]:
            t.next = ListNode(int(c))
            t = t.next

        return h

本文链接:https://cs.pynote.net/ag/leetcode/202203171/

-- EOF --

-- MORE --