题目描述 牛客网
- 如果一个链表中包含环，如何找出环的入口节点？
-
例如，在如下图所示的链表中，环的入口节点是节点3
题目解读
- 剑指Offer 139
- 书上思路挺想详细的，请自行翻阅
- 第一步：确定一个链表中是否包含环。受到面试题22的启发，我们可以用两个指针来解决这个问题。和前面问题一样，定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就包含环；如果走得快的指针走到了链表的末尾都没有追上第一个指针，那么链表就不包含环
- 第二步：得到环中节点数目。我们在前面提到判断一个链表里是否有环时用到了一快一慢指针。如果两个指针相遇，则表明链表中存在环。两个指针相遇的节点一定是在环中。可以从这个节点出发，一边继续向前移动一边计数，当再次回到这个节点时，就可以得到环中节点数了
- 第三步：找到环的入口。我们还是可以用两个指针来解决这个问题。先定义两个指针 p1 、p2 指向链表的头节点。如果链表中的环有 n 个节点，则指针 p1 先在链表上向前移动 n 步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口节点时，第一个指针已经围绕着环走了一圈，又回到了入口节点
代码
- 第一轮代码
#include<iostream>
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
class Solution {
public:
// 找到环中共有多少个节点
// 此处注意必须注意编写代码时要考虑指针为空的情况，要不然程序太不健壮了..
int find_loop_sum(ListNode* pHead){
int n = 0;
ListNode *kuai = NULL;
ListNode *man = NULL;
if(pHead->next){
man = pHead -> next;
}else{
return 0;
}
if(man->next){
kuai = man -> next;
}else{
return 0;
}
while(kuai != man){
if(kuai->next && kuai->next->next){
kuai = kuai -> next -> next;
man = man -> next;
}else{
return 0;
}
}
// 代码运行到这里的时候，kuai man 指针指向同一个节点且均在环中，
// 此时，让一个指针在原地等待，一个在环中跑一圈，当另一个指针再次回到原点时，则遍历完环中节点数目
while(kuai -> next != man){
kuai = kuai -> next;
n++;
}
n++;
cout<<n<<endl;
return n;
}
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(!pHead){
return NULL;
}
int n = find_loop_sum(pHead);
if(n == 0){
return NULL;
}
ListNode *p1 = pHead;
ListNode *p2 = pHead;
for(int i=0; i < n; i++){
p1 = p1 -> next;
}
while(p1 != p2){
p1 = p1 -> next;
p2 = p2 -> next;
}
return p1;
}
ListNode* create(){
ListNode *p;
ListNode *head = NULL;
ListNode *tail = NULL;
ListNode *loop = NULL;
for(int i=1; i <= 6; i++){
p = new ListNode(i);
if(i == 3){
loop = p;
}
if(!head){
head = p;
}
else{
tail -> next = p;
}
tail = p;
}
tail -> next = loop;
return head;
}
void print_Node(ListNode *head){
for(int i = 1; i <= 10; i++){
cout<<head->val<<" ";
head = head->next;
}
cout<<endl;
}
};
main(){
Solution ss;
ListNode *head = NULL;
ListNode *loop = NULL;
head = ss.create();
ss.print_Node(head);
// cout<<ss.find_loop_sum(head)<<endl;
loop = ss.EntryNodeOfLoop(head);
cout<<loop->val<<endl;
}
- 第二轮代码
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead){
if(pHead == NULL){
return NULL;
}
// 找到环中节点数目
int count = find_loop_count(pHead);
if(count == 0){
return NULL;
}
// 找到环的入口
ListNode* p1 = pHead;
ListNode* p2 = pHead;
for(int i=0; i < count; i++){
p1 = p1->next;
}
while(p1 != p2){
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
// 找到环中节点数目
int find_loop_count(ListNode* pHead){
ListNode* kuai = NULL;
ListNode* man = NULL;
// 第一步先判断是否有环
if(pHead->next != NULL && pHead->next->next != NULL){
man = pHead->next;
kuai = pHead->next->next;
}else{
return 0;
}
while(kuai != man){
if(kuai->next->next != NULL && man->next != NULL){
kuai = kuai->next->next;
man = man->next;
}else{
return 0;
}
}
// 找到环中数目
int count = 0;
while(kuai->next != man){
kuai = kuai->next;
count++;
}
count++;
return count;
}
};
2023.5.25 第三轮
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
#include <cstddef>
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
if (!pHead) return pHead;
int n = GetLoopCount(pHead);
std::cout << "n = " << n << std::endl;
if (n == 0) return NULL;
ListNode* p1 = pHead;
ListNode* p2 = pHead;
for (int i=0; i<n; i++) {
p1 = p1->next;
}
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
int GetLoopCount(ListNode* pHead) {
int n = 0;
bool flag = false;
// 1、一快一慢两个指针先判断是否有环
ListNode* kuai = pHead;
ListNode* man = pHead;
while (kuai->next && kuai->next->next) {
kuai = kuai->next->next;
man = man->next;
if (kuai == man) {
flag = true;
break;
}
}
if (flag) {
kuai = kuai->next;
while (kuai != man) {
kuai = kuai->next;
n++;
}
n++;
}
return n;
}
};
总结展望
- 越来越发现剑指 offer 题目是真好，自己见识还是太浅显
- 认真，努力，勤奋
