↓Skip to main content

判断链表中是否有环

·149 words·1 min
WFUing
Author
WFUing
A graduate who loves coding.
Table of Contents

  • 链接：https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9
  • 升级版-链表中环的入口结点：https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
  • 链表中倒数最后k个结点：https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9

难点
#

链表的题目很早刷过，现在有些生疏了，再回顾一遍。

代码
#

解法一

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) {
        ListNode fast = head, slow = head;
        while (fast != null && slow != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return false;
            }
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

解法二

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode pos = head;
        // 哈希表记录访问过的结点
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            // 判断结点是否被访问
            if (visited.contains(pos)) {
                return true;
            } else {
                // 结点记录添加到哈希表中
                visited.add(pos);
            }
            // 遍历
            pos = pos.next;
        }
        return false;
    }
}