|
1.在单链表中删除倒数第K个节点
思路一：直接遍历一遍求出链表的长度，然后找到第N-K个节点之前的一个节点，因为要删除。
思路二：画图发现，我们要走到N-K这个位置，使用双指针，先让一个链表走K步，然后两个指针一块移动即可。但是要找到的是前一个所以要另做处理。
ps：一定注意要验证K的正确性。
2.删除链表的中间节点
思路：双指针，一个每次走两步，一个每次走一步即可。（画图看）
扩展：找到三等分点，有两个点，每次一个链表走三步一个走一步，可以找到一个点，然后记录走一步的指针一共走n次，该指针再走n步即可知道第二个点。（画图看）
3.反转单链表（递归注意！！！！！）
思路：每一个子问题都相同，而且满足循环不变性。一个pre，一个next，一个cur，while使用cur指针判断边界，最终返回pre指针。（画图看，子问题：next=cur.next head.next=pre pre=head head=next）
//递归方式
Node * reverseList(List head)
{
//如果链表为空或者链表中只有一个元素
if(head == NULL || head->next == NULL)
{
return head;
}
else
{
//先反转后面的链表，走到链表的末端结点
Node *newhead = reverseList(head->next);
//再将当前节点设置为后面节点的后续节点
head->next->next = head;
head->next = NULL;
return newhead;
}
}
ps：newhead一直都是最后一个节点。递归到最后节点的时候才开始反转。
扩展一：双链表进行反转的时候一定注意子问题指针的指向（需要改变next和last指针），
扩展二：反转部分单链表，注意判断要不要换头，如果不要那么要找到from-1和to+1个节点，然后反转链表在进行连接即可。
4.判断一个链表是否为回文结构
思路一：使用栈结构，全部入栈然后出栈与原链表比较；还可以先找到中间节点然后只入栈一半然后出栈进行比较。
思路二：不使用空间，先找到中间节点，然后反转后半部分，然后与前半部分进行比较。
5.将单向链表按某值分成左边小、中边相等、右边大的形式
思路一：把节点全部放入数组中，然后转化为荷兰国旗问题，在把链表进行连接。
思路二：申请三个变量每个进行连接各自的元素即可，最后进行拼接....
6.复制含有随机指针节点的链表
思路一：因为有随机指针，那么拷贝rand指针的时候都要从头指针开始遍历才可；可以考虑空间换时间的思路，把所有指针的节点都存到字典中（key代表数字值，value代表节点本身），然后在遍历原指针在依次连接new节点的next和rand指针。
思路二：trick思路，因为不能快速找到rand指针元素，所以先直接在原链表上交叉拷贝一份变为：1-1'-2-2'-3-3'这种，然后遍历链表每次走两步，不就可以快速找到rand的元素了。
7.（高位在前的）链表相加
思路：注意高位在前，那么考虑使用栈结构然后对应位置相加；考虑直接链表逆序在相加。
8.判断两个无环链表是否相交
思路一：只要相交那么在他之后全都相交，所以可能链表不等长，需要先计算出来长度（在这还能检验是否相交）长的链表先走，然后在一块走。
思路二：可以申请两个栈，然后遍历两个链表，然后一块出栈进行比较即可。
ps：记录每个相同的值，直到不同的值出现。
思路三：直接暴力法，对l1的每一个节点都跟l2进行比较。
9.将单链表的每K个节点之间逆序
思路：类似于区间反转链表，注意要特殊处理反转头部的情况（因为from-1指针为空）。然后每步都要先找到from-1和to+1这两个指针因为要连接新链表，每次还要检查K值不够则不需要转换。
ps：反转链表可以使用栈来进行简化操作，只要注意处理from-1指针和为空的情况即可，不需要to+1的连接。
10.删除无序单链表中值重复出现的节点
思路一：使用哈希表，如果出现就删除当前节点即可，pre.next=cur.next。
思路二：对每个节点与后面所有节点进行比较判断是否删除，注意保留pre指针。
ps：就是空间换时间的思路，一定要注意。
11.在单链表中删除指定值的节点
ps：需要注意，一定要找准前继节点，而且是与当前节点不同的前继节点。
12.搜索二叉树转化为双向链表
思路一：考虑队列，把搜索二叉树中序遍历然后在出队依次串起来。
思路二：使用递归分解子问题，使用后序遍历，可以找到该节点的前驱和后继指针然后左指针指向前继节点改变了两个指针，右指针指向后继节点；使用中序遍历，可以找到前驱节点其实也可以实现，也是改变两个指针pre.right=root root.left=pre；所以说，递归问题一定要找到好的子问题来做。
ps：中序遍历，pre起始是nullptr，更新的时候下一个节点的pre节点就是当前的node节点。
扩展：双向链表转化为二叉树，可以每次找到中间的节点，然后前驱指针指向左子树，后继指针指向右子树然后递归的做下去。
13.按照左右半区的方式重新组合单链表
思路：先使用快慢指针找到中间节点，把链表分成两个，再把两个链表进行合并需要注意链接与移动的顺序。
ps：一种合并可以是申请一个节点依次从两个链表中取节点，比较好操作；另一种是直接在左链表上进行链接，操作需要注意先后顺序和指针的移动（需要存储每次右半区的剩余节点）。
14.判断链表是否有环以及环的入口位置
判断是否有环：快慢指针即可判断。
入口位置：可以类比找倒数第K个节点的位置，先找出环的节点数（在环里面，只要再走一遍回到原位置即可）把这个数字当成倒数第K个节点，先让一个指针走K步然后两个指针在一块走，直到相遇（因为有环，所以尾部指向环的入口节点了）！
ps：这个找环的入口位置，跟倒数第K个节点进行类比的思路很好。
15.旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置。
思路一：赋值一整个链表，进行拼接，然后删除前n-k个即可。
思路二：使用双指针，（其实就是找倒数第k个节点而已），进行拼接即可。
ps：注意就是导数第k个节点的变形而已。
16.链表排序
快排：
允许交换值。
思路一：直接交换值进行快排即可。
不允许交换值。
思路二：使用两个头节点进行拼接即可。
归并：
常数时间复杂度，还是需要每2，4，8，16进行归并！不然可以直接使用栈。
插入排序：
维护一个有序的链表，cur节点需要进行并入到有序链表中，需要从头开始遍历进行插一个空。
选择排序：
（不允许交换值）可以使用一个头结点，每次选一个最小节点进行拼接即可。
（允许交换）每次选一个最小结点，需要一个指针确定有序链表的边界。
冒泡排序：（直接交换值）
每次经过冒泡都可以选择一个最小的节点（从前向后冒泡），需要一个尾指针来进行跟进。
ps：链表的排序，一定要注意是否可以直接交换值，注意是否可以用一个头节点来简化操作，注意要用一个指针进行边界的限制！
总结：其实链表这块要注重代码的鲁棒性，一定要提前处理空指针，一个节点，两个节点，在头结点插入删除，尾节点插入删除，插入删除需要先找到pre节点等等需要注意的。 | 
转播
