链表总结
1. 链表的引入
2. 链表
2.1 链表的概念及结构
2.2 链表的分类
2.3 链表的实现
2.3.1 具体功能函数
2.3.2 代码：
3. LeetCode链表典型题目
3.1 移除链表元素
3.2 反转链表
3.3 链表的中间结点
3.4 删除链表的倒数第 N 个结点
3.5 链表中倒数第k个节点
3.6 合并两个有序链表
3.7 分割链表
3.8 回文链表
3.9 相交链表
4. 链表成环问题
4.1 给定一个链表，判断链表中是否有环
4.2 返回入环的第一个结点
5. 复制带随机指针的链表
6. 双向带头循环链表
6.1 函数实现
6.2 代码：
6.3 顺序表与链表的优异
7. 总结
1. 链表的引入
当我们在使用顺序表时，出现的很多场景都会引起空间及其时间上复杂度的问题：
问题：
- 中间/头部的插入删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
2. 链表
2.1 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
可以形象的看成：
而在数据结构中，链表中每一个节点大致由其三块数据对应的集体所代表：
- 数据域：存放信息的位置
- 指针域：结点之间相连的关键（可以看成火车之间的连接的链子）
- 自身地址：即结点本身的位置，指针域连接的就是这个部分。（可以看成每一节车厢的编号）
在下面的介绍中，会发现将创建结点的代码单独放在了一个函数中，我们知道，一个变量出了函数的作用域会由于栈帧的操作释放该变量，导致返回值不能使用，但是这个为什么可以呢？
当然，通过malloc等动态开辟的空间不会主动释放，其开辟的空间是在堆空间上实现的，并不是栈；在之前的动态内存开辟中，说明了这一类的只能由free函数释放掉，并且一定要及时的释放掉，否则会发生内存泄漏。
2.2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
单向或者双向
- 带头或者不带头
- 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
2.3 链表的实现
2.3.1 具体功能函数
// 1、无头+单向+非循环链表增删查改实现 typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; // 动态申请一个结点 SLTNode* BuySLTNode(SLTDataType x); // 单链表打印 void SListPrint(SLTNode* phead); //单链表销毁 void SListDestory(SLTNode** pphead); // 单链表的头插 void SListPushFront(SLTNode** pphead, SLTDataType x); // 单链表尾插 void SListPushBack(SLTNode** pphead, SLTDataType x); // 单链表的尾删 void SListPopBack(SLTNode** pphead); // 单链表头删 void SListPopFront(SLTNode** pphead); // 单链表查找 SLTNode* SListFind(SLTNode* phead, SLTDataType x); // 在pos之前插入 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); // 在pos后面插入 void SListInsertAfter(SLTNode* pos, SLTDataType x); // 删除pos位置 void SListErase(SLTNode** pphead, SLTNode* pos); // 删除pos后面位置 void SListEraseAfter(SLTNode* pos);
在实现之前，我们需要先弄懂每个函数传参的参数类型不一样的原因是什么？
不难发现，传二级的原因是需要改头，因为头的类型原本就是SLTNode* 类型的，如果函数参数也为此类型，则函数改变的将会是形参，形参只是实参的一份临时拷贝，改变形参，实参不会发生改变，因此，当我们需要改头时，在test.c中传入的应该是：函数名(&plist),而因为plist是头，故定义的时候就是 SLTNode plist*，因此，需要传入二级指针。
2.3.2 代码：
由于本篇文章过长，为了不占用过多篇幅影响小伙伴们食用，单链表实现的代码点下方链接即可（这是我的代码仓库的部分呜呜呜）：
当我们梳理完整的代码之后，单链表的优势和缺陷也就显而易见了：
优势： 头插头删，时间复杂度为O(1)。
缺陷：当我们想要删除除了头的任何一个当前位置时，需要记录他的前一个节点，这就需要去寻找这个节点，因此时间复杂度为O(N)。
既然有缺陷，那么有没有方式去弥补这个缺陷呢？
想要删除当前节点的数据，若是能通过删除下一个节点从而删除当前节点岂不是完美了吗，于是，在这里用一种方式：将下一个节点的数据覆盖到当前的节点的数据之上，再将下一个节点删除。 这样，我们通过数据的迁移间接性的将此位置的节点删除，并且时间复杂度是O(1)。
但实际上，这不过是一个取巧的方式而已，链表终究只是适合头部的改变，尾部改变还不如用顺序表。
由于链表的oj题极为重要，作者将会对典型题目进行详细的讲解：( 还不赶紧拍手叫好（滑稽）)
3. LeetCode链表典型题目
3.1 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1 输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7 输出：[]
提示：
- 列表中的节点数目在范围
[0, 104]内 1 <= Node.val <= 500 <= val <= 50
具体思路： 创建一个新的头节点，但不存储数据，若节点数据不等于val，则将此与其连接，同时记录尾部，方便下一次连接。
代码实现： 时间复杂度为O(N)
//不是val尾插到新链表,对新链表创建个尾指针 struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode)); newhead->next = NULL; struct ListNode* tail = newhead;//哨兵位 struct ListNode* cur = head; while(cur) { struct ListNode* next = cur->next;//记录下一个节点位置 if(cur->val != val) { tail->next = cur; cur->next = NULL;//断开 tail = cur; } cur = next; } return newhead->next; }
3.2反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
思路：
- 法1：三指针迭代
通过改变箭头的方向从而使链表反向，在截断原本的链接之前，需要用指针记录下一位置，以便进行向后迭代。
直到cur为空。
struct ListNode* reverseList(struct ListNode* head) { if (head == NULL || head->next == NULL) return head; struct ListNode* prev = NULL, * cur = head, * next = head->next; while (cur) { //反转链表 cur->next = prev; //迭代 prev = cur; cur = next; if (next) next = next->next; } return prev; }
- 法2：头插
创建新头newHead = NULL,将旧链表每一个节点取下来进行头插
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* newHead = NULL; while (cur) { struct ListNode* next = cur->next; cur->next = newHead; newHead = cur; cur = next; } return newHead; }
3.3链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
思路： 对于中间节点来说，比较直白的方法是计算链表的长度，折半之后在遍历进行迭代，思路很清晰并且正确。但第二种思路才是这个题中的最优解：定义两个指针，即快慢指针，慢指针走一步的同时快指针走两步，直到快指针->next为空。这时慢指针指向的位置即为中间节点。
struct ListNode* middleNode(struct ListNode* head){ if(head->next == NULL) return head; struct ListNode* slow = head; struct ListNode* fast = head; while(fast&&fast->next)//&&的特点，上一个不成立，下一个条件不判断，不会出现野指针的情况 { slow = slow->next; fast = fast->next->next; } return slow; }
3.4 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]
思路： 这里我们仍然利用双指针的方法，即前后指针：通过观察不难发现，让前指针先走N步，再让后指针与前指针同时走，直到后指针为空，前指针就走到了倒数第N个节点，再让prev记录上一个节点的位置，从而进行连接。
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){ if(head == NULL) return head; if(head->next == NULL&&n==1) return NULL; struct ListNode* cur = head; struct ListNode* fast = head; struct ListNode* slow = head; while(n--) { fast = fast->next; } struct ListNode* prev = NULL; while(fast) { prev = slow; slow = slow->next; fast = fast->next; } if(prev == NULL) { head=head->next; } else { prev->next = slow->next; } return head; }
链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.
与上题寻找的思路一样，只不过不是删除，而是直接返回slow。需要注意k>链表长度，fast需要提前判空
struct ListNode* getKthFromEnd(struct ListNode* head, int k){ if(head == NULL || k == 0) return NULL; struct ListNode* fast = head; struct ListNode* slow = head; while(k--) { if(fast == NULL) return NULL; else fast = fast->next; } while(fast) { fast = fast->next; slow = slow->next; } return slow; }
3.6合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
思路： 采用归并的思想，新建一个头结点，两个链表节点依次比较，哪个小哪个连接，并将小的对应的链表向下一个节点。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ if(list1 == NULL) return list2; if(list2 == NULL) return list1; struct ListNode* cur1 = list1; struct ListNode* cur2 = list2; struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode)); newHead->next = NULL; struct ListNode* tail = newHead; while(cur1 && cur2) { if(cur1->val<cur2->val) { tail->next = cur1; cur1 = cur1->next; } else { tail->next = cur2; cur2 = cur2->next; } tail = tail->next; } if(cur1) tail->next = cur1; if(cur2) tail->next =cur2; return newHead->next; }
3.7分割链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于x 的节点都出现在 大于或等于x 的节点之前。
你需要 保留 每个分区中各节点的初始相对位置。（将题干改成了需要保留，原题为不需要保留）
示例 1：
输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2 输出：[1,2]
提示：
- 链表中节点的数目在范围
[0, 200]内 -100 <= Node.val <= 100-200 <= x <= 200
思路：通过创建两个新的头节点（哨兵位）将此链表进行按照条件进行归类，并分别记录尾部，归类之后将两个链表进行连接，最后free掉两个节点
struct ListNode* partition(struct ListNode* head, int x){ struct ListNode* less = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* large = (struct ListNode*)malloc(sizeof(struct ListNode)); less->next=NULL; large->next=NULL; struct ListNode* lesstail=less; struct ListNode* largetail=large; struct ListNode* cur=head; while(cur) { if(cur->val<x) { lesstail->next=cur; lesstail=lesstail->next; } else { largetail->next=cur; largetail=largetail->next; } cur=cur->next; } largetail->next=NULL; lesstail->next=large->next; head=less->next; free(less); free(large); large=less=NULL; return head; }
3.8回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1] 输出：true
示例 2：
输入：head = [1,2] 输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解题步骤：对此，总结的一句话就是，不能重复造轮子（能偷懒就偷懒），我们可以利用上面的中间节点+反转链表进行操作：
即： 找到中间节点之后将前后分割开并对后半部分进行反转，对这两个链表节点的数据域的val进行一一对比，不管原本链表是奇数还是偶数长度，分割开即便是一奇一偶，判断时若有一个链表迭代到空（此时一奇一偶），即为回文链表，因为中间的数本来也只有一个。
注：即便分割成两个链表后不将前半部分的链表最后指向空，一样可以判断，因为前半部分最后指向的肯定是原本中间的那个，即后半链表反转之后的最后一个。此代码即为此。
//反转链表： struct ListNode* reverseList(struct ListNode* head) { if (head == NULL || head->next == NULL) return head; struct ListNode* prev = NULL, * cur = head, * next = head->next; while (cur) { //反转链表 cur->next = prev; //迭代 prev = cur; cur = next; if (next) next = next->next; } return prev; } //链表的中间节点： struct ListNode* middleNode(struct ListNode* head){ if(head->next == NULL) return head; struct ListNode* slow = head; struct ListNode* fast = head; while(fast&&fast->next)//&&的特点，上一个不成立，下一个条件不判断，不会出现野指针的情况 { slow = slow->next; fast = fast->next->next; } return slow; } bool isPalindrome(struct ListNode* head){ struct ListNode* mid = middleNode(head); struct ListNode* rmid = reverseList(mid); while(head && rmid) { if(head->val != rmid->val) return false; head = head->next; rmid = rmid->next; } return true; }
但这时会有小伙伴们想到，直接反转链表并将此链表与反转后的一一对比是不是也可以？答案是否定的，因为反转此链表之后，原本的链表内部同样会反转，相当于自己与自己比较，无论是不是回文结构，都会返回true,因此，若想用这个方法，必须在通过开辟节点或者用数组存储原本数据与其反转之后的进行比较，但不论是开辟新节点还是用数组，都是很挫的方式，若有别的方法解决，就不要用此方法
3.9相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点
图示两个链表在节点 c1 开始相交 ：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。
提示：
listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
进阶： 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
对于此题，直接想到的方法就是暴力求解，即每个节点都用一个完整的链表扫描，必然会扫描到（这种方式过于麻烦呜呜呜）。但，由于作者本着：没有优解，博客不写的原则，那么开始介绍优解的方法：
思路： 通过题干不难发现，由于不知道两个链表到相交位置的距离，我们无法利用两个指针去寻找，但是如果两个链表的起始位置到相交节点的距离相同，我们就可以用两个指针进行一起一步一步的前进，他们必然会相遇。可惜的是，两个链表的起始位置到相交节点的距离也不一定就相同呀，那么现在的问题就变成了如何让两个指针到交点的距离相同。
当我们从后往前看的时候，不难发现，两个链表的长度差1，并且，我们发现，若是让下面的链表的指针从b2开始扫描，那么就符合我们上述所提到的：距离相同 。这个时候，你一定会发觉并且猜想到，让长的链表先移动两个链表长度之差的长度 ，就可以让其并行，即到相交位置的距离相同。想到这里，这道题目，也就迎刃而解了。（恭喜恭喜）
经过一系列的揣测与分析加上有点蒙题的猜想，那就……可以上代码了：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if(headA == NULL ||headB == NULL) return NULL; struct ListNode* curA = headA, *curB = headB; int lenA = 1; //找尾节点 while(curA) { curA = curA->next; ++lenA; } int lenB = 1; while(curB) { curB = curB->next; ++lenB; } struct ListNode* longList = headA, *shortList = headB; if(lenA<lenB) { longList = headB; shortList = headA; } //长的链表先走差距步 int gap = abs(lenA-lenB); while(gap--) { longList = longList->next; } while(longList!=shortList) { longList = longList->next; shortList = shortList->next; } return longList; }
那么对其进行相交与不相交的情况的归类，发现最后一个例子仅仅是一个链表也可以看成为相交链表（不禁让想象变得丰富起来）
