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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 0 -> 8
Subscribe to see which companies asked this question.
仓鼠翻译一下题目：给你两个非空链表，每个链表代表一个数，把这两个数加起来，返回结果。结果也是以链表的形式返回。
稍微特殊一点的地方是，给的链表是按数字的每一位倒着给的，比如 123 一百二十三 给的链表是 3 -> 2 -> 1
这样如果输入 (2 -> 4 -> 3) 和 (5 -> 6 -> 4) 两个链表，代表 342 和 465，加出来的结果应该是 807，返回的结果应该是 7 -> 0 -> 8
这就是一个简单的链表节点的定义。包含两部分：
Paste_Image.png
next 是一个钩子，钩住链表里的下一个节点，所以我们能从每个节点顺到下一个节点。value 是节点要存的值，什么都可以，我们现在用一个 int 作为例子。
节点当然不带头结点，链表才带头结点呀。
所以大家知道链表是什么了嘛？链表就是一系列这样的节点，第一个连着第二个，第二个连这第三个…… 这样。第一个节点称为头结点，最后一个节点称为尾节点
继续讲链表哈。我们跟数组来对比一下。数组是内存里一段连续的空间，第一个元素挨着第二个元素，第二个元素挨着第三个元素…… 而链表在内存里可能是不连续的，第一个节点和第二个节点内存上并不连续，但是第一个节点有个 next 指针指向第二个节点，第二个节点有个 next 指针指向第三个节点……
不要被“指针”这俩字吓到，我发现很多人都怕这个词，但实际咱们平常写 OC 的，@property (nonatomic, strong) LinkListNode* next; 这就是一个指针。就按着一个 property 去理解就好。
好好，接着讲：刚才代码示例了节点的结构，下面来示例一下链表的结构。就是记住了俩节点，头结点和尾节点。
Paste_Image.png
有时候连尾节点都不给，比如本题，只给了头结点。但你通过 next 一路顺下去，也能找到尾节点了。
简单讲一下链表怎么操作。插入一个节点，分为三种情况：最基本的情况，比如之前是 a -> b，要插在 a、b之间，就改成这样 a->c->b 即可，让 a.next = c, c.next = b；另外两种特殊情况，插在头结点之前，只需让 c->a，然后把链表的 head 从 a 改成 c；插在尾节点之后，只需让 b->c ，然后把链表的 tail 从 b 改到 c。
删除一个节点，大家可以类推一下……
访问某个位置的节点，比如找第 5 个节点，只能从头结点找齐，头结点的 next 找第二个节点，第二个的 next 找第三个节点…… 一直找到第5个
我们已经有了数组，为啥还要用链表呢？我们来对比一下数组和链表的优势和劣势。数组的优势是，它的空间是连续的。所以我可以“随机访问”，比如 我现在就要知道第10个元素，我可以 array[10]，而链表就完全不行，像刚才说的，得从头结点开始往下顺。数组访问某个位置的元素，时间复杂度是 O(1) 而链表是 O(n)
但数组也有劣势，就在于插入和删除。比如我要删除数组第3个元素，那么第2个元素和第4个元素之间就会出现一个空档。数组的空间是连续的，为了不让它出现空档，我们必须把第4个元素挪到第3个元素的位置，第5个元素挪到第4个元素的位置…… 一个一个往前挪。而链表就很轻松，直接把第二个节点的 next 指向第四个节点，第三个节点就从链表里掉下来啦。
数组在中间位置插入和删除，时间复杂度是 O(n) 而链表是 O(1)
最后一个next指向NULL
网友评论