LeetCode 2. 两数相加

发表于 | 更新于 | 分类于

题意

给出两个非空的链表用来表示两个非负的整数，他们的位数是按照逆序存储的，每个结点存储一位数字。求他们相加后的结果（用链表表示）。

思路

  • 直接模拟。因为是逆序给出的所以直接遍历一遍按位相加就好了，实现过程中用一个变量记录进位情况。时间复杂度$O(max(m, n))$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode res(0), *p = &res, *newp;
        int sum, carry = 0;
        while(l1 != NULL || l2 != NULL || carry)
        {
            sum = 0;
            if(l1 != NULL)  sum += l1 -> val;
            if(l2 != NULL)  sum += l2 -> val;
            sum += carry;
            carry = sum / 10;

            newp = new ListNode(sum % 10);
            p->next = newp;
            p = newp;

            l1 = l1 ? l1 -> next : NULL;
            l2 = l2 ? l2 -> next : NULL;
        }

        return res.next;
    }
};

总结

关于访问ListNode里的成员时，是用.直接访问还是用->呢？答：当当前变量是一个实体成员(如上面代码中定义的res)时用.，因为它包含了成员；当是一个指针时，用->，因为它只是指向一个指向地址的指针，并没有实体。

自己的联想——如果给出的是从高位到低位存的呢？可以先将两个链表都逆置一下，然后再进行上面的操作。写到这又想到了备战考研期间看的王道数据结构这本书上的问题，之前打ACM时解决的问题和书上给出的考试要考的内容有挺大差别的，一开始有些不适应，觉得这么简单还用写？。不过后来习惯后觉得还挺巧妙的，其中印象较为深刻的就有对链表的逆置操作（将前一半元素和后一半元素交换位置转化为了先整体逆置、再对前半部分逆置、再对后半部分逆置）。

Donate comment here
0%