链表OJ题讲解---试金石含金量

1. 环形链表（详细讲解）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) 
//判断以head为头节点的单链表是否存在环
{ListNode* slow=head,*fast=head;while(fast && fast->next)//这是快指针，最先到达链表的末尾，当快指针指向为空，就说明没有环{slow=slow->next;fast=fast->next->next;if(fast==slow)return true；/如果fast==slow，说明链表是有环的}return false;//当fast都走到空了，还是没有出现fast==slow的情况，说明链表没有环
}

这道题我们还是使用快慢指针的方法，快指针走两步，慢指针走一步，如果链表是有环的，快指针会在环中追上慢指针。

也就是说，通过快慢指针的追击，若能相遇则链表有环；若快指针先走到链表末尾，则无环。

这里我们来看一下画图的解释。

1.1 环形链表面试拓展问题证明！！！

1.1.1 说明为什么会相遇，有没有可能会错过，永远追不上？

这里我们还是画图分析。

slow⼀次走⼀步，fast⼀次⾛2步，fast先进环，假设slow也走完⼊环前的距离，准备进环，此时fast和slow之间的距离为N，接下来的追逐过程中，每追击⼀次，他们之间的距离缩小1步。

总结一下这个问题，当环的周长为C的时候，当fast 和 slow相差N步，N为偶数的时候，第一轮一定可以追上，但是N为奇数的时候，第一轮追不上，而距离就会变成C-1。

如果C是奇数，那么C-1就是偶数，第二轮一定可以追上；如果C是偶数，那么C-1就是奇数，就追不上，而且永远都追不上。

1.1.2 slow一次走1步，fast一次走3步 4步 5步 n步，请证明

fast走3步追上，N%3 == 0             fast走4步,N%3==1                   fast走3步追上，N%3==2

                          N-3                                       N-3                                                          N-3         

                          N-6                                       N-6                                                          N-6

                          3                                           1                                                                2

                          0                                           -2（C-2）                                                -1(C-1)

反思：同时存在N是奇数而且C是偶数的情况，那么永远追不上这个假定是正确的吗，真的会存在永远都追不上的情况吗？

slow走的距离是：L；
fast走的距离是：L+x * C+C-N(假设走了x圈）

slow进环的时候，假设fast已经在环里面转了x圈

这里列等式，3L=L+x * C+C-N;化简完成为2L=（x+1)* C-N

                                                                偶数=（x+1)* 偶数-奇数

只有奇数-奇数才等于偶数，但是（x+1)*偶数一定是偶数，所以反证出N是奇数而且C是偶数的情况不可能同时出现，永远追不上的条件是不成立的。

结论：一定是可以追上的，N是偶数第一轮就追上了；

                                ​​​​​​​        ​​​​​​​    N是奇数第一轮追不上，C-1是偶数第二轮就追上了

这里需要一定的数理知识，所以需要耐心推导，曾经面试考官考题，重视！！！

1.1.3 求环的入口节点

题目要求：判断链表是否有环，并且如果有环的话，找到环的入口节点。

N（假设slow进环走了N步，就跟fast相遇）；

环的周长是C；

快慢指针在进环之前走了L步

slow走的路程：L+N
fast走的路程：L+x*C+N

fast走的路程是slow的2倍，
2（L+N)=L+x*C+N
化简：L=x* C-N===>L=(x-1) * C+C-N,x >=1 而且是整数

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* slow=head,*fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;//相遇if(fast==slow){ListNode* meet=slow;//定义一个指针meet，此时slow所在的位置是快慢指针在环内的相遇点while(meet != head)//head指针从链表的头节点出发，meet从快慢指针在环内的相遇点出发{meet=meet->next;head=head->next;}return meet;//相遇的节点就是链表环的入口节点}}return NULL;
}

2.随机链表的复制

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {Node* cur=head;//拷贝节点入原节点的后面while(cur){//为拷贝的节点申请空间Node* copy=(Node*)malloc(sizeof(Node));copy->val=cur->val;//先复制数值copy->next=cur->next;//把拷贝节点copy插入原节点cur的后面cur->next=copy;//让拷贝节点的next指向原节点的下一个节点cur=copy->next;//让原节点的next指向拷贝节点}//控制randomcur=head;//重新开始遍历链表while(cur){Node* copy=cur->next;//获取cur对应的拷贝节点copyif(cur->random==NULL){cur->random=NULL;}else{copy->random=cur->random->next;//copy的random指向该原节点random所指向的节点对应的拷贝节点，因为原节点的next就是其对应的拷贝节点}cur=copy->next;//继续向后循环}//把拷贝节点取下来尾插成为新链表，然后恢复原来的链表（不恢复也可以）Node* copyhead=NULL,* copytail=NULL;cur=head;//再次遍历while(cur){Node* copy=cur->next;//获取当前原节点cur对应的拷贝节点copyNode* next=copy->next;//用与后期恢复链表和遍历原链表if(copytail==NULL){copytail=copyhead=copy;}else{copytail->next=copy;//copy的值尾插copytail=copytail->next;//向后移动}cur->next=next;//用于恢复原链表cur=next;//将cur继续向后移动}return copyhead;//返回拷贝链表的头节点
}