牛客题霸NC04题解
程序员文章站
2022-04-15 17:47:45
判断链表中是否有环牛客题霸NC93难度:Easy题目描述判断给定的链表中是否有环,你能给出空间复杂度[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tufwc43W-1604905749303)(https://www.nowcoder.com/equation?tex=O(1)]%5C)的解法么?题目解答1. Set+遍历遍历链表,将遍历的每个节点放到一个Set里。如果遍历过程中发现Set中已经存在该节点,则代表链表存在环;如果遍历到末尾,则代表链表无环。...
判断链表中是否有环
难度:Easy
题目描述
判断给定的链表中是否有环,你能给出空间复杂度[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tufwc43W-1604905749303)(https://www.nowcoder.com/equation?tex=O(1)]%5C)的解法么?
题目解答
1. Set+遍历
遍历链表,将遍历的每个节点放到一个Set里。如果遍历过程中发现Set中已经存在该节点,则代表链表存在环;如果遍历到末尾,则代表链表无环。
import java.util.*;
/**
* 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) {
Set<ListNode> set = new HashSet<>();
while(head != null){
if(set.contains(head)){
return true;
}
set.add(head);
head = head.next;
}
return false;
}
}
时间复杂度:O(n)
空间复杂度:O(n)
2. 快慢指针相遇
设置快慢两个指针,如果两个指针最终相遇,代表链表存在环;若快指针到达链表末尾,则代表不存在环。
/**
* 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;
}
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null){
if(slow == fast){
return true;
}
slow = slow.next;
fast = fast.next.next;
}
return false;
}
}
时间复杂度:O(n)
空间复杂度:O(1)
本文地址:https://blog.csdn.net/nuolve3993/article/details/109578159