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