【算法题解】10. 环形链表

这是一道简单题，题目来自：leetcode

题目

给你一个链表的头节点 head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
如果链表中存在环 ，则返回 true。 否则，返回 false。

示例1：

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

示例2：

输入：head = [1,2]
输出：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;
}

复杂度分析

时间复杂度 $O(N)$：需要访问链表中的每一个节点，时间复杂度为链表长度n。
空间复杂度 $O(1)$：只需要记录快慢指针的两个变量，空间复杂度为常数。