题目
206 反转链表
给你单链表的头结点 head ，请你反转链表，并返回反转后的链表。
自己思路：遍历链表记录其值，再依次修改链表的值。
题解：直接更改结点指针，使其指向前一个结点。需要新设p和q指针辅助变向。
160 相交链表
给你两个单链表的头结点 headA 和 headB ，请你找出并返回两个单链表相交的起始结点。如果两个链表不存在相交结点，返回 null 。
自己思路：嵌套遍历两链表，因为无环，所以找到第一个相等的结点返回即可，从此结点开始相交。（错误，因为链表长度不一，遍历时会提前终止，数组存储再比较也会有这个问题。）
题解：
- 哈希表
遍历headA，用哈希表存储，再遍历headB，若哈希表中存在headB结点，则返回该结点。
用哈希表而非一般数组，因为哈希表有固定用法可以直接在集合中搜索headB结点。 - 双指针
用pa与pb同步遍历两链表。在两指针未指向同一结点时，当pa走到headA末尾时，pa开始遍历headB，当pb走到headB末尾时，pb开始遍历headA。
如果两链表相交，则两指针遍历对方链表时 会指向相交的同一结点。
如果链表不相交，要么他们长度相等，两指针同时遍历到链表末尾，指向空。要么长度不等，两指针同步遍历自己链表与对方链表，同时到达对方链表末尾，指向空。
21 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。
自己思路：
迭代法。在两链表都非空时，遍历并选择值更小的放入 带头结点的新链表，其中一个链表为空时退出循环，将非空的链表链接到新链表中。
题解：
递归法。对链表的结点进行比较，选择值更小的链表， 链接其后移一位后 递归调用的该函数 并返回，当其中一个链表为移动到末尾 为空时，链接返回非空链表。
86 分隔链表
给你一个链表的头结点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的结点都出现在 大于或等于 x 的结点之前。
你应当 保留 两个分区中每个结点的初始相对位置。
自己思路：误以为是快排题目，无从下手哈哈。
题解：维护两个带头结点的链表，分别存储小区和大区的结点，遍历完成后链接两个链表即可。注意大区末尾结点应指向空，否则其仍链接之前的结点，会产生闭环。
142 环形链表 ||
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
自己思路：
哈希表法。遍历各结点并用哈希表记录，同时判断该节点的next是否已在哈希表中，存在则有环。
题解：
快慢指针法，适用于寻找距离尾部第K个节点、寻找环入口、寻找公共尾部入口等。
快指针每次走两步，慢指针每次走一步。若有环则两者必然相遇，可由条件推导出从快慢指针相遇点到入环点的距离 等于 链表头部到入环点的距离。此时另设一指针指向链表头部，和慢指针同步移动，两者相遇则该点为入环点。
若无环则快指针不断移动必将移动至链表末尾，其next为空。
92 反转链表 ||
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表
自己思路：
穿针引线法。遍历从开始到 right 的各个结点，小于 left 的结点存进新链表，left 到 right 的结点进行反转。再次遍历 已反转的部分结点，存进新链表。最后链接right之后的链表。
题解：
注意新建链表是链接各区间链表的一般做法。
穿针引线（头插法）：不断将后一个结点移到反转区间最开始的位置。
新链表的next指向原链表，小于 left 时与其同步移动，left 到 right 的结点进行头插法反转。遍历结束即为反转后的链表。
138 复制带随机指针的链表
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点。随机指针指向的节点索引范围为从 0 到 n-1；如果不指向任何节点，则为 null 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
自己思路：没有想到用哈希表存储两链表。可以由原链表和新链表的一一对应关系想到使用哈希表进行复制。
题解：
哈希表法。遍历原结点，新建值和原结点相同的新结点，将 原结点作为key，新结点作为value 存进哈希表中。再次遍历原结点，通过key获取哈希表中的新结点，根据原结点的 next 和 random 设置新结点的 next 和 random。注意新结点的 next 为原结点的next所指向的结点 对应的新结点。
迭代+结点拆分法。遍历原结点，在每个原结点之后插入值相同的新结点（形成1-1‘-2-2’-3-3‘），插入后，新结点的 next 为原结点的 next（原来1->next 为2，现在1’->next为2）。再遍历插入新结点后的链表，设置新结点的 random，注意新结点的 random 为原结点的 random 的复制版，即 random->next。
817 链表组件
给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。
返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。
自己思路：（找断点很绕）遍历链表结点，找出断点，并判断其前一个结点是否为断点，不为断点则组件加一。能在nums中找到则标记flag，找不到则为断点。注意末尾结点可能为断点和非断点，需要处理。
题解：找组件的起始位置。分两种情况，一是结点值在nums中且结点在链表开始位置，二是结点值在nums中且其前一个结点不在nums中。注意在nums中找某个值可用循环也可用哈希集合。
数据结构
哈希表
哈希表一般由 数组+链表 或 数组+二叉树 实现。
set：只保存关键字，关键字即值。
一般用于在集合中搜索元素（set.count(K)），即判断一个元素是否出现在集合中。
map：保存关键字和值，关键字唯一。
链表反转
注意新建链表是链接各区间链表的一般做法。
//一般反转：
//eg:1234,curr指向1（链表头），p和q都为nullptr。
p = curr->next; //p指向2 3
curr->next = q;//1链接到q(初始为nullptr) 2-1
q = curr;//q指向1 2
curr = p; //curr指向2 3
//一轮结束后：1的next变向，由2变为空。 1-null，234. 两轮21，34.
//头插法反转:
//pre永远为待反转部分的前一个结点(前面没有时可新建一个头结点, pre 指向新结点;
//curr为待反转部分的第一个结点,不变化
//next永远为curr的下一个结点，链接改变会变化
//eg:1234,curr指向1（链表头）
pre->next = curr; //初始化 pre（新建头节点）链接到1
//while(区间长度--)
next = curr->next; //next指向2, 3
cur->next = next->next;//1链接到3, 1->4
next->next = pre->next;//2链接到1, 3->2
pre->next = next; //pre链接到2, ->3
//一轮结束后：2134 3214
|