【算法题解】10. 判断链表是否有环

这是一道简单题。

题目来自：https://leetcode.cn/problems/linked-list-cycle/description/

题目

给你一个链表的头节点 head，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

如果链表中存在环，则返回 true。否则，返回 false。

示例1:

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例2:

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例3:

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

解法一：循环标记

循环遍历每一个节点并标记为已访问，如果可以再次访问到已经访问过的节点则返回true，否则最后返回false。

Java 代码实现

/**
 * 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;
        }
        Set<ListNode> visited = new HashSet<>();
        while(head != null){
            if(visited.contains(head)){
                return true;
            }
            visited.add(head);
            head = head.next;
        }
        return false;

    }
}

Go 代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 * Val int
 * Next *ListNode
 * }
 */

func hasCycle(head *ListNode) bool {
    visited := make(map[*ListNode]bool)
    for head != nil {
        if visited[head] {
            return true
        }
        visited[head] = true
        head = head.Next
    }
    return false

}

复杂度分析

时间复杂度 O(N)：需要访问链表中的每一个节点，时间复杂度为链表长度 n。

空间复杂度 O(N)：需要记录每个访问过的节点，空间复杂度为链表的长度 n。

解法二：快慢指针

快慢指针法，让快指针每次走2步，慢指针每次走1步，如果存在环，那么快指针最终一定会再次追上慢指针。

Java 代码实现

/**
 * 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;
        ListNode slow = head;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                return true;
            }
        }

        return false; 
    }
}

Go 代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 * Val int
 * Next *ListNode
 * }
 */

func hasCycle(head *ListNode) bool {
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if slow == fast {
            return true
        }
        
    }
  return false;
}