牛客算法题记录三(判断链表是否有环)
-
-
-
- 题目
- 题解
-
- 1、快慢指针解决
- 2、存放到集合中
-
-
题目
判断给定的链表中是否有环。如果有环则返回true,否则返回false
题解
1、快慢指针解决
最简单的一种方式就是快慢指针,慢指针每次走一步,快指针每次走两步,如果相遇就说明有环,如果有一个为空说明没有环。代码比较简单
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
if (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
2、存放到集合中
还可以把节点存放到集合set中,每次存放的时候判断当前节点是否存在,如果存在,说明有环,直接返回true,比较容易理解
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
Set<ListNode> set = new HashSet<>();
while (head != null) {
// 如果重复出现说明有环
if (set.contains(head))) {
return true;
}
// 否则就把当前节点加入到集合中
set.add(head);
head = head.next;
}
return false;
}
}