判断单链表是否有环

判断单链表是否有环

题目描述:输入一个单向链表,判断链表是否有环?

分析:通过两个指针,分别从链表的头节点出发,一个每次向后移动一步,另一个移动两步,两个指针移动速度不一样,如果存在环,那么两个指针一定会在环里相遇。这其实就是追赶游戏,跑的快的肯定能追的上慢的。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
bool hasCircle(Node *head){
Node *slow,*fast;
slow = fast = head;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
circleNode = fast;
return true;
}
}
return false;
}

另一种解法

分析: 利用一个Map和一个指针p,从头结点出发,依次判断每个节点的指针是否存在于map中,如果存在则表示有环,且p就是环的入口点,否则循环结束后p==null,没有环;

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool hasCircle(Node *head){
if(head == NULL || head->next == NULL){
return false;
}
Node *p = head;
Map map = new Map();
while(p != NULL){
if(map.contains(p)){
return true;
}
map.put(p);
p = p->next;
}
return false;
}
文章目录
  1. 1. 判断单链表是否有环
  • 另一种解法
  • |