描述:
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。
输入描述: 输入分为2段,第一段是入环前的链表部分,第二段是链表环的部分,后台将这2个会组装成一个有环或者无环单链表。
返回值描述: 返回链表的环的入口结点即可。而我们后台程序会打印这个节点。
简述
给定链表的头结点,若有环则找到链表的入环节点。
算法一 : 哈希表
时间复杂度:O(N)
思路:
从头开始将每个节点存入哈希表中,如果第一次遇到该节点已经在哈希表中那么该节点为入口节点。如果链表能被遍历完,说明不存在环,则返回NULL。 原因:1. 链表中每个节点的地址是不一样的,那么我们分别将这些地址存进哈希表中,如果该节点已经在哈希表中,那么说明我走了重复的路。
2. 对于重复的路那么肯定是环的节点,而入口节点也是环的一个节点,也是被存入哈希表中的第一个环的节点。 图解:
代码:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
unordered_set<ListNode*> hash;
ListNode* EntryNodeOfLoop(ListNode* pHead) {
if(pHead){
ListNode* t=pHead;
if(hash.find(t)==hash.end()){
hash.insert(t);
if(pHead->next) return EntryNodeOfLoop(pHead->next);
}
else return t;
}
return NULL;
}
};
算法二 : 双指针
时间复杂度:O(N)
思路:
1. 利用两个指针,快指针 j ,慢指针 i 。j 的速度是 i 的两倍,让他们不断往后走,直到两者相遇为止。 2. 让 j 回到头结点 ,然后再让 j 和 i 以相同速度走,i 与 j 再次相遇的点即为入口节点。
具体证明如图所示 图解:
代码:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
if(!pHead) return NULL;
ListNode* i=pHead;
ListNode* j=pHead;
while(j&&j->next){
i=i->next;
j=j->next->next;
if(i==j) break;
}
if(!j||!j->next) return NULL;
j=pHead;
while(j!=i){
i=i->next;
j=j->next;
}
return j;
}
};
返回值描述: 返回链表的环的入口结点即可。而我们后台程序会打印这个节点。
简述
给定链表的头结点,若有环则找到链表的入环节点。
算法一 : 哈希表
时间复杂度:O(N)
思路:
从头开始将每个节点存入哈希表中,如果第一次遇到该节点已经在哈希表中那么该节点为入口节点。如果链表能被遍历完,说明不存在环,则返回NULL。 原因:1. 链表中每个节点的地址是不一样的,那么我们分别将这些地址存进哈希表中,如果该节点已经在哈希表中,那么说明我走了重复的路。
2. 对于重复的路那么肯定是环的节点,而入口节点也是环的一个节点,也是被存入哈希表中的第一个环的节点。 图解:
代码:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
unordered_set<ListNode*> hash;
ListNode* EntryNodeOfLoop(ListNode* pHead) {
if(pHead){
ListNode* t=pHead;
if(hash.find(t)==hash.end()){
hash.insert(t);
if(pHead->next) return EntryNodeOfLoop(pHead->next);
}
else return t;
}
return NULL;
}
};
算法二 : 双指针
时间复杂度:O(N)
思路:
1. 利用两个指针,快指针 j ,慢指针 i 。j 的速度是 i 的两倍,让他们不断往后走,直到两者相遇为止。 2. 让 j 回到头结点 ,然后再让 j 和 i 以相同速度走,i 与 j 再次相遇的点即为入口节点。
具体证明如图所示 图解:
代码:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
if(!pHead) return NULL;
ListNode* i=pHead;
ListNode* j=pHead;
while(j&&j->next){
i=i->next;
j=j->next->next;
if(i==j) break;
}
if(!j||!j->next) return NULL;
j=pHead;
while(j!=i){
i=i->next;
j=j->next;
}
return j;
}
};
简述
给定链表的头结点,若有环则找到链表的入环节点。
算法一 : 哈希表
时间复杂度:O(N)
思路:
从头开始将每个节点存入哈希表中,如果第一次遇到该节点已经在哈希表中那么该节点为入口节点。如果链表能被遍历完,说明不存在环,则返回NULL。
原因:1. 链表中每个节点的地址是不一样的,那么我们分别将这些地址存进哈希表中,如果该节点已经在哈希表中,那么说明我走了重复的路。
2. 对于重复的路那么肯定是环的节点,而入口节点也是环的一个节点,也是被存入哈希表中的第一个环的节点。
图解:
代码:
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: unordered_set<ListNode*> hash; ListNode* EntryNodeOfLoop(ListNode* pHead) { if(pHead){ ListNode* t=pHead; if(hash.find(t)==hash.end()){ hash.insert(t); if(pHead->next) return EntryNodeOfLoop(pHead->next); } else return t; } return NULL; } };
算法二 : 双指针
时间复杂度:O(N)
思路:
1. 利用两个指针,快指针 j ,慢指针 i 。j 的速度是 i 的两倍,让他们不断往后走,直到两者相遇为止。
2. 让 j 回到头结点 ,然后再让 j 和 i 以相同速度走,i 与 j 再次相遇的点即为入口节点。
具体证明如图所示
图解:
代码:
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { if(!pHead) return NULL; ListNode* i=pHead; ListNode* j=pHead; while(j&&j->next){ i=i->next; j=j->next->next; if(i==j) break; } if(!j||!j->next) return NULL; j=pHead; while(j!=i){ i=i->next; j=j->next; } return j; } };