一、环形链表
1.定义（概念）
所谓的环形链表，无非是这一种，如图所示
这样的链表，就可以称为环形链表。
2.如何判断是否为环形链表
给定一链表，我们怎么判断是否为环形链表呢？
接下来我们认识一下快慢指针的概念
1.快慢指针
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。
就是以表头为初始位置，我们定义fast、slow两个结点，指向head头节点，fast每一次，走两个结点，slow每一次走一个结点，如果有环，必然会相遇（fast==slow），注意哦，是指针地址相等哦！如果无环的话，就会fast更快的走到链表末尾，指向NULL
2.为什么快指针一次走两个结点
假设链表带环，两个指针最后都会进入环里面，快指针先进入环，慢指针后进入环、当慢指针刚计入环的时候，可能就和快指针相遇了，最差的情况是相距环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况（无法相遇），因此，在慢指针走到一圈之前，快指针肯定能追上慢指针的，即相遇！
如图所示：
如图所示：
3.例题分析
这是例题链接，环形链表
题目如下：
AC代码如下：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode *fast=head; struct ListNode *slow=head; // if(fast!=NULL||fast->next!=NULL){ // return false; // } while(fast!=NULL&&fast->next!=NULL){ slow=slow->next; fast=fast->next->next; if(fast==slow){ return true; } } return false; }
1.while循环，因为head为头节点，head为NULL，说明为空链表，head->next为NULL，说明只有一个结点，无法构成环。
2.我们使用while循环，使用快慢指针，fast步长为2，slow步长为1，如果fast==slow返回为true（有环），循环结束之后，返回false（无环）
还有一种比较暴力的解法：
代码如下：
while(head!=NULL){ if(head->val==100000){ return true; } head->val=100000; head=head->next; } return false;
第二个可以用快慢指针的题目
如图：
我们使用快慢指针的思路是，fast如果与slow同时移动的话，移动一次，fast与slow指向的指针差距都会加一，所以，倒数第k给结点，只需要，fast与slow距离为k的时候，两者再以都以步长为1移动，fast，移动到NULL时，slow指向的就是倒数第k个节点
代码如下：
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pListHead ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // // write code here // if(pListHead==NULL){ // return NULL; //判断是否为NULL // } // struct ListNode*cur=pListHead; // int count=0; // while(cur!=NULL){ // count++; // cur=cur->next; // } // //得到了结点个数 // if(count==0){ // return NULL; //如果空链表，自然返回NULL // } // int num=count+1-k;//这是num得到倒数第k个结点 count-k+1 // if(k>count||k<=0){ //如果k大于count，当然是不行的，小于0也不行，都返回NULL // return NULL; // } // while(--num){ //然后进行循环即可 // pListHead=pListHead->next; // } // return pListHead; //快慢指针问题，设计两个指针，fast和slow两种，然后先移动fast指针k步，然后一起移动两个指针，直到fast移动到NULL的时候，slow就是倒数第k个结点 struct ListNode*fast=pListHead; struct ListNode*slow=pListHead; while(k--){ if(fast==NULL){ return NULL;//如果为空链表，那么就返回NULL } fast=fast->next; } while(fast){ fast=fast->next; slow=slow->next; } return slow; }
while循环移动k次，然后同时步长为1移动，直到fast为NULL，这就是使用快慢指针的思路。
当然被//的是普通的做法，一并附上
二、相交链表
如图：
1.例题分析
2.解法分析
第一种如图所示：
代码如下：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if(headA==NULL||headB==NULL){ return NULL; } struct ListNode*p=headA; struct ListNode*q=headB; while(p!=q){ p=p==NULL?headB:p->next; q=q==NULL?headA:q->next;//因为比较的是指针的地址，所以如果指向NULL之后，还可以继续找到头节点 //1.结点数相同的时候，一次遍历就能得到是否有相交，这个结点就是p指向的位置，如果没有，p正好指向null //2.如果结点数不同的时候，那么因为不同，所以当结点数小的那个遍历一边的时候，结点数大的还没完成，这样永远差一个结点数之差的位置，然后继续接上上两个头节点，这样第二轮，就是在尾部对齐的情况下，起始位置相同，这样一轮必然能得到答案 } return p; }
第二种解法分析：
主要是，先遍历得到两条链表的长度，pq分别指向链表头节点headA、headB然后将长的那个链表的头节点给p结点，然后得到两链表结点个数之差，num=lenA-lenB，然后将p结点移动num次，while循环，然后再同时移动p和q结点，进行判断是否有相交结点
代码如下：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if(headA==NULL||headB==NULL){ return NULL; } // struct ListNode*p=headA; // struct ListNode*q=headB; // while(p!=q){ // p=p==NULL?headB:p->next; // q=q==NULL?headA:q->next;//因为比较的是指针的地址，所以如果指向NULL之后，还可以继续找到头节点 // //1.结点数相同的时候，一次遍历就能得到是否有相交，这个结点就是p指向的位置，如果没有，p正好指向null // //2.如果结点数不同的时候，那么因为不同，所以当结点数小的那个遍历一边的时候，结点数大的还没完成，这样永远差一个结点数之差的位置，然后继续接上上两个头节点，这样第二轮，就是在尾部对齐的情况下，起始位置相同，这样一轮必然能得到答案 // } // return p; //第二种做法 //目的是，我们想让他们尾部对齐，然后在同长度的情况下，遍历，这样就能找到相交结点，或者NULL struct ListNode*p=headA; struct ListNode*q=headB; if(headA==NULL||headB==NULL){ return NULL; } //取得第一个A链表的长度 int lenA=0; while(p!=NULL){ lenA++; p=p->next; } int lenB=0; while(q!=NULL){ lenB++; q=q->next; } //找到之后，将最大的结点数都给A 就是交换位置 p=headA; q=headB; if(lenA<lenB){ //交换结点长度 int temp=lenA; lenA=lenB; lenB=temp; //交换链表头节点 struct ListNode*node=p; p=q; q=node; } //这样得到的是A为最长结点 //两个结点相互减去 int count=lenA-lenB; while(count--){ p=p->next; } while(p!=q){ p=p->next; q=q->next; } return p; }
总结
了解了快慢指针这一概念，对于环形链表会进行判断了，相交链表的问题，也可以实现了，不过值得一提的是，力扣讨论区里面，真的不少好玩有趣的解法。
比如经典的 return true; （50%答案）真的好逗！！！
