链表经典算法实现思路
链表⭐️⭐️⭐️
1：链表的概念与结构
概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
组成：由一个个结点（结构体）组成，由指针链接。
定义链表节点的结构
structSListNode{SListdatatype data;structSListNode*Next;//指向下一个节点的指针}2：二级指针的使用
因为要形参改变实参，所以传入了结构体指针的地址，使得能够形参改变实参。
因此出现了二级指针。
3：算法题目
1：203. 移除链表元素 - 力扣（LeetCode）
思路一：双指针
思路二：创建一个新链表
2：206. 反转链表 - 力扣（LeetCode）
思路一：创建新链表，头插；
思路二：创建三个指针（方向翻转）（难度⭐️⭐️⭐️）
思路三：递归；（难度⭐️⭐️⭐️⭐️）
3：21. 合并两个有序链表 - 力扣（LeetCode）
思路一：前插；
4：876. 链表的中间结点 - 力扣（LeetCode）
思路一：快慢指针（差速法）；(两分法，同理可推1/3，2/3)
5：循环列表的解决环形链表的约瑟夫问题_牛客题霸_牛客网
思路一：创建循环链表，双指针。（模拟淘汰的过程）
思路二：只针对m=2的情形，就是最简单记忆法。
把人数 n 写成二进制：
- 把最高位的 1 移到最后
- 得到的二进制数就是答案
例：n=5 → 二进制101
最高位 1 移到最后 →011→ 3
存活位置是3
思路三：数学的递归；
6：面试题 02.04. 分割链表 - 力扣（LeetCode）
思路一：直接判断+前插。
思路二：对思路一简化，接受上一次前插节点的位置。少了多次while循环。
思路三：创建两个链表，分别定义为大链表，小链表。
7：链表分割_牛客题霸_牛客网
8：返回倒数第K个节点。面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）
思路一：双指针，第一个指针先走k步，之后同时走，那么当前一个走到空时，后面就为倒数第k个节点。
4：链表的分类
5：双向链表
不改变传入指针，只需要以一级指针就行。
6：环形链表的解释
例题1:链表的回文结构_牛客题霸_牛客网
思路一：创建一个反转之后的链表，然后逐步比较。（满足时间复杂度，不满足空间复杂度）。
思路二：先找中间节点，然后逆置后半部分节点，之后在进行逐步比较（没有开辟新的空间，时间复杂度为O（N））
例题二：160. 相交链表 - 力扣（LeetCode）
思路一：不能从后往前，因为它的next只能唯一。（不能反转或逆置），另外不能根据值判断，要用地址判断。
思路二：直接判断尾指针，如果尾指针相等，说明两个链表一定相交。然后在等距查找。计算两个链表的长度，然后在等距的地方开始同时往前走，进行比较地址。
例题三：141. 环形链表 - 力扣（LeetCode）
问题一：如何判断一个链表带不带环
问题二：如何判断链表已经入环了
解决方法，快慢指针。
如何快指针追上满指针，则表明带环。
新问题一：那么为什么一定会相遇，有没有可能错过，永远追不上？请证明
很简单。假设slow指针入环时，fast指针与slow的指针相差N步，那么slow指针往前走一步，距离加一，fast指针向前走两步，距离减二，那么走一步，总体距离减一，那么经过N步，fast追上slow指针。
新问题二：slow走一步，fast走三四五六七步，一定能追上吗？请证明。
一定能追上，虽然可以推出一个永远追不上的条件，但很容易分析这个条件不存在。
例题四：142. 环形链表 II - 力扣（LeetCode）
需要简单的推导，得出L=C-N;因此相遇之后同时走，再相遇就是环的入口。
例题五：138. 随机链表的复制 - 力扣（LeetCode）
把拷贝节点插入到原节点的后面。
最后一步一定要对新复制的链表结尾进行判空
还有一定要注意复制时一定要对random进行检查。例如：
while(ptemp!=NULL){ptemp->next->random=ptemp->random->next;ptemp=ptemp->next->next;}//如果此时ptemp->random的值是NULL,那么对NULL访问会报错，要改为while(ptemp!=NULL){// 只有原节点的random不为NULL时，才赋值复制节点的randomif(ptemp->random!=NULL){ptemp->next->random=ptemp->random->next;}ptemp=ptemp->next->next;}