4. 链表成环问题
4.1 给定一个链表，判断链表中是否有环
由于有扩展问题，我们先解决题目：
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
提示：
- 链表中节点的数目范围是
[0, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
进阶： 你能用 O(1)（即，常量）内存解决此问题吗？
对于成环问题，如果是环，那么链表迭代的过程中不会截止，但是我们不能根据是否截止进行判断是不是环，这样只会运行超时，因此，需要采用一定的特殊技巧：
利用快慢指针，即快指针一次走两步，慢指针一次走一步，当慢指针进入环后，转化思想为快指针追赶慢指针：根据相对运动，每次移动快指针都会离慢指针更进一步，这就使得二者一定会在圈中相遇。即为真。
如果不是环，快指针一定先走到末端。
bool hasCycle(struct ListNode *head) { if(head == NULL) return false; struct ListNode* slow = head,*fast = head; while(fast && fast->next)//一次走两步，防止出现野指针需要判断两个条件 { slow = slow->next; fast = fast->next->next; if(slow == fast) { return true; } } return false; }
【扩展问题】
为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
快指针一次走3步行吗？
不一定。慢指针在进圈后，快指针以相对慢指针两个单位两个单位的追赶，如果N为奇数（N代表两个指针之间的距离），距离就会变成：N-2,N-4,……3,1,-1。当变成-1时，又是一个新的开始，此时二者相距C-1个长度，C为环的周长，如果c-1是奇数，那么就永远不会相遇，因此不一定。
快指针一次走M步行吗？
对此，可与一次走三步的类似，需要看N与C的关系。
慢指针一次走N步，快指针一次走M步行吗？（M>N)
只要是在环中，并且M比N大1个单位，那么就可以认为快指针相对慢指针靠近一步，这样相当于遍历所有可能性，一定会相遇。
总结：只要fast比slow快一步，无论他们一次走几个单位，都一定可以相遇。
4.2返回入环的第一个结点
对于这种类型的，先证明一下无疑是最好的学习方式：
假设进环前的长度是L，假设环的长度是C，假设入口点到相遇点距离为X
1.公式推导：
fast走的距离 = 2*slow走的距离；
slow走的距离：L+X；
fast走的距离：L+N*C+X;(fast转了N圈，N>=1)
注： 为什么slow走的不是L+n*C+X呢? 即为什么slow在圈里一定走了不到一圈就相遇了呢？我们知道当slow刚刚进圈时slow与fast之间的距离一定小于C-1,fast一次走两步，slow一次走一步，距离逐渐减小，即一定走了小于C-1次就会相遇，因此推出此时slow走了不到一圈。
即：根据二倍关系：2(L+X) = L+X+N*C，即L = N * C - X;进一步得出：
L = ( N − 1 ) ∗ C + C − X L = (N-1)*C+C-X
L=(N−1)∗C+C−X
结论：一个指针A从头开始走，一个指针B从相遇点开始走，他们会在入口点相遇。
2.转化成相交问题
当我们通过快慢指针找到相遇点记录下来以后，可以想象把此相遇节点与下一节点断开，记录下一个节点为链表B的头，并记录起始位置为链表A的头，这样通过相交链表的方法，就能求得入环的第一个节点，也就是链表的第一个交点
那么我们可以尝试解决这道题目：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
进阶： 你是否可以使用 O(1) 空间解决此题？
- 公式推导法：
struct ListNode* hasCycle(struct ListNode *head) { if(head == NULL) return NULL; struct ListNode* slow = head,*fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { return slow; } } return NULL; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* meet = hasCycle(head); if(meet == NULL) return NULL; struct ListNode* begin = head; while(1) { if(begin == meet) { return begin; } begin = begin->next; meet = meet->next; } return NULL; }
相交法：
struct ListNode* hasCycle(struct ListNode *head) { if(head == NULL) return NULL; struct ListNode* slow = head,*fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { return slow; } } return NULL; } 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; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* meet = hasCycle(head); if(meet == NULL) return NULL; struct ListNode* newheadB = meet->next; meet->next = NULL;//必须断开，否则在求相交链表在求长度时会死循环。 struct ListNode* newheadA = head; struct ListNode* newmeet = getIntersectionNode(newheadA,newheadB); meet->next = newheadB;//恢复环 return newmeet; }
相信这个代码大家已经看出来了，复用的两个函数不正是判断是否有环的函数和相交链表的函数吗？只不过判断是否有环的函数的返回值稍微改了一下，因此，只要掌握思路，写出的代码一定是有联系的。
5. 复制带随机指针的链表
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
提示：
0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。
这是一道有挑战性的题目。因此，我把他单拿出来放在这里。这道题本身的难度在于random指针，通过常规暴力的方法，我们需要的是将每一个random指针的位置给记录下来，从而当处理拷贝链表的过程中，再利用双层循环将每个特定的位置的random指向这个拷贝链表相对应的位置，但是为什么不能根据val值从而链接呢？因为val的值本身是允许重复出现的，只有通过具体位置才能锁定，因此需要创建数组来记录位置（思路清晰，实现起来繁琐，自己也是想了好久），下面的代码实现就是这样的思路：
1.暴力解决
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* BuySLTNode(struct Node* node) { struct Node* newnode = (struct Node*)malloc(sizeof(struct Node)); newnode->next = NULL; newnode->random = NULL; newnode->val = node->val; return newnode; } struct Node* copyRandomList(struct Node* head) { //创建复制的链表 struct Node* newhead = (struct Node*)malloc(sizeof(struct Node)); newhead->next = NULL; struct Node* ntail = newhead; struct Node* cur = head; while(cur) { ntail->next = BuySLTNode(cur); ntail = ntail->next; cur = cur->next; } // 记录节点个数， cur = head; int n = 1; while(cur) { n++; cur = cur->next; } cur = head; //将位置记录到count数组里，count数组的每一个元素记录该节点random指针指向的位置 struct Node* repcur = cur; int* count = (int*)calloc(n,sizeof(int));//开辟数组记录每一个random指向的数据的位置 int i = 0; while(cur) { int order = 0; while(repcur) { if(cur->random == NULL) { count[i++] = n-1; break; } if(cur->random == repcur) { count[i++] = order; break; } order++; repcur = repcur->next; } repcur = head; cur = cur->next; } i = 0; //通过之前的数组找到复制之后的位置 struct Node* newcur = newhead->next; struct Node* newcur1 = newhead->next; while(newcur) { int j=0; while(newcur1) { if(j == count[i]) { newcur->random = newcur1; break; } j++; newcur1 = newcur1->next; } newcur1 = newhead->next; newcur = newcur->next; i++; } free(count); return newhead->next; }
2.在链表本身进行拷贝
再次本着无优解博客不写的原则，既然暴力的解决了，那为什么还要有优解呢？ emm……这是一个很痴呆的问题，有好的方法，谁会不愿意用呢？那下面，我们就来说说这个美妙的方法：
上文提到了，难点在于random指针的拷贝，但我们又根据原链表很清晰的知道random指向的位置，因此，我们就要靠着原链表，在原链表的基础上进行改造：
/
在此基础上进行改造：
在每一个节点的后方，拷贝一个与该节点一模一样的节点（当然地址肯定不一样喽）即图中的copy节点插入到原链表，这样就可以对random指针进行下面操作:
copy->random = cur->random->next;//后者代表着仍然是copy的节点，因为有指向next
这样就可以完美的解决random指针的问题啦。
因此应该进行以下步骤：
- 1.复制节点插入原链表中，并对copy的random进行赋值(关键操作)。
- 2.将copy的节点拿出来尾插编程新的链表。
- 3.在第二步的同时将原链表恢复原状
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { //1.插入copy节点 struct Node* cur = head; struct Node* copy = NULL; struct Node* next = NULL; while(cur) { next = cur->next; copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; //连接到原链表 cur->next = copy; copy->next = next; //迭代往后走 cur = next; } //2.更新copy->random cur = head; while(cur) { copy = cur->next; if(cur->random == NULL) copy->random = NULL; else copy->random = cur->random->next; //迭代往后走 cur = cur->next->next; } //将其copy的节点尾插，并还原原链表 cur = head; struct Node* copyhead = NULL; struct Node* copytail = copyhead; while(cur) { copy = cur->next; next = copy->next; if(copyhead == NULL) { copyhead = copytail = copy; } else { copytail->next = copy; copytail = copytail->next; } //重新还原原链表 cur->next = next; //迭代 cur = next; } return copyhead; }
6. 双向带头循环链表
6.1函数实现
// 2、带头+双向+循环链表增删查改实现 typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* next; struct ListNode* prev; }ListNode; // 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* plist); // 双向链表打印 void ListPrint(ListNode* plist); // 双向链表尾插 void ListPushBack(ListNode* plist, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* plist); // 双向链表头插 void ListPushFront(ListNode* plist, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* plist); // 双向链表查找 ListNode* ListFind(ListNode* plist, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的结点 void ListErase(ListNode* pos);
与单链表不同的是，这里无论是什么函数传的都是一级指针，原因是此结构是带头的，即哨兵位，哨兵位的数据域不存储，并且传进去的哨兵位为真正哨兵位的形参，但是其next和prev分别记录了实际节点的地址，因此，这里都用一级指针完全可以解决。
顺序表与链表的优异
7. 总结
这篇文章呕心沥血，是我目前写的时间最长的文章，不过到这里也就收尾了，本篇文章侧重的是实现链表所需要注重的细节及经过链表oj强训所带来的一系列的新的逻辑与方法，相信读到这里的你对于链表的掌握会上升一个非常大的台阶，即便这样，仍要多加训练，因此，将我的链表oj仓库放在这里以便大家食用（以后刷的链表也会在这里），一起加油哇！
