7.18 链表

leetcode 反转单链表

思路：非递归，辅助变量newhead，为最后的返回值。
递归，要从后向前返回，注意递归结束条件为当前值的next为空即返回。

leetcode 整合两个排序链表

思路：新建newhead辅助节点用于记录排序后的新链表头节点，用指针ptr指向newhead，作为遍历的指针。

leetcode 判断链表是否有环

思路：快慢指针，快指针走两步，慢指针走一步，两者都不为空，且两者相等，则有环，返回。也可以用map或set记录遍历的节点，若出现过，则有环。

leetcode 求两条单链表的交点

思路：两个遍历的指针分别向前，为空就重新赋值为另一条链表的头。注意应先判断两指针是否相等，再更新指针。这样不会漏掉链表长度为1的情况。

leetcode 判断回文链表

思路：回文链表指链表对称。思路一，利用栈先入后出的思想，从前到后入栈，然后比较栈内元素和链表元素是否一致。思路二，利用快慢指针找到链表中点，利用栈记录慢指针的路径，然后比较链表前后两段是否相同。思路三，不使用额外空间，先用快慢指针找到中点，然后将后半段链表反转，注意链表结尾的节点值为奇数和偶数要不同处理。之后比较前后两段是否相同。

leetcode 链表排序，将K个有序链表合并，整合两个排序链表

思路：要求复杂度为nlogn，用归并排序。将链表分开为两段，然后分别排序，最后将排序后的两段整合到一条链表中。三个题目的解法一样。

leetcode 深度拷贝带有随机指针的链表

思路：需要两次遍历，map记录原链表的映射关系，vec记录新节点。第二次遍历更新对应关系。注意需要在vec中多添加一个空节点，这样最后一个节点的random指针可以被更新到，不用单独操作。

leetcode 从链表末尾移除第N个元素

思路：N始终合法。首先需要判断链表是否为空或者是否只有一个节点，返回空。然后将工作指针ptr前移N个元素，如果ptr为空，说明N和链表长度相同，此时返回head->next。接着，用pre指针跟着ptr一起向前移动，直到ptr为最后一个节点，此时pre为第N-1个节点，执行移除操作即可。

leetcode 将链表表示的两个树相加

思路：注意进位的加。只要两个链表和进位三者任意一个不为空，就可以继续执行加法操作。