三、链表 ➡️
一些常用技巧：
- 链表增加哑结点 dummy，就不用单独判断 head 节点了。
ListNode* dummy = new ListNode(0, head); - 删除节点 dummy：
delete dummy; - 区分
cur.val和cur->val：使用cur.val时，cur 是一个结构体，而使用cur->val时，cur 是一个指向结构体的指针。 - 基于 3，注意区分节点和节点的指针的初始化：
- 初始化节点
ListNode* Node = new ListNode(0，NULL); - 初始化一个节点的指针
ListNode* node = head;
- 初始化节点
3.1 链表元素相加
【2. 两数相加】
【21. 合并两个有序链表】
注意返回的节点需要是原来的节点，所以相当于需要改变两个链表指向的节点，因此需要两个指针分别指向链表的还未排序的节点，然后比较当前的节点，直到遍历完至少有一个链表。
【23. 合并 K 个排序链表】
【148. 排序链表】
3.2 删除链表节点
【19.删除链表的倒数第 N 个结点】
我用的方法就很朴素，找要删除节点的前驱节点（第length-n-1个节点）。需要特别考虑链表有 n 个元素，删除倒数第 n 个的情况，这时候没法找到前驱，所以直接返回head->next。看了下题解，比较值得借鉴的方法是双指针法，也是只用遍历一次的方法：使用两个指针同时遍历，first 比 second 超前 n 个节点，当 first 遍历到链表的末尾时，second 就恰好处于待删除的节点，很妙。
【237.删除链表中的节点】
只能访问删除节点的情况下把该节点删除。因为一般来说要删除一个节点，更方便的方法是找到它的前驱节点。这题就要稍微绕一点弯，只需要把下一个节点的值赋给当前的节点，然后把下一个节点删除即可。
3.3 链表元素重构
【328.奇偶链表】
【138. 复制带随机指针的链表】
3.4 反转链表
【24. 两两交换链表中的节点】
【92. 反转链表 II】
给定一个区间，反转区间内的链表
【206. 反转链表】
反转整个链表，用三个指针遍历反转链表，这里需要注意的一个地方是：反转第一个节点时，不能让第二个节点再指向第一个节点，否则第一个和第二个节点会形成一个环。在我的解法里，增添了一个尾部的哑节点，这样可以少一些判断，而且第三个指针也可以重复更新，不用每个循环重新定义一个指针，减少空间开销。
【2074. 反转偶数长度组的节点】
（周赛）区间值递增，反转偶数区间的链表（若最后一个区间少于递增数量那么如果是偶数个同样反转，否则不反转）
3.5 判断链表性质
【234.回文链表】
判断链表是否是回文的，最简单的办法就是遍历一次链表，然后把值存储在一个数组中，然后问题转换成判断一个数组是否是回文串，双指针迎刃而解。我写这题的想法略麻烦，我用数组存储了一半元素，然后它们再逐个和后半段数组进行比较，虽然确实时空复杂度都提高了一些，但代码属实不够优雅，因为需要考虑奇数个和偶数个序列的差别。
【141.环状链表】
判断链表有没有环。朴素的方法就是用一个哈希表unordered_set<ListNode*>来存储链表的元素，然后不断遍历判断。更巧妙的方法就是用一快一慢两个指针（一个每次指向下一个元素，另一个每次指向下两个元素），如果两个指针重合的话，那么就说明是有环的。