欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

牛客题霸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中已经存在该节点,则代表链表存在环;如果遍历到末尾,则代表链表无环。...

判断链表中是否有环

牛客题霸NC93

难度: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