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

﹏ヽ暗。殇╰゛Y 2024-03-29 15:47 50阅读 0赞

#### 文章目录 ####

*   *  题目
     *  解法一：循环标记
     *   *  Java 代码实现
         *  Go 代码实现
         *  复杂度分析
     *  解法二：快慢指针
     *   *  Java 代码实现
         *  Go 代码实现
         *  复杂度分析

> 这是一道简单题，题目来自：[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 ) O(N) O(N)：需要访问链表中的每一个节点，时间复杂度为链表长度`n`。  
空间复杂度  O ( N ) O(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 ) O(N) O(N)：需要访问链表中的每一个节点，时间复杂度为链表长度`n`。  
空间复杂度  O ( 1 ) O(1) O(1)：只需要记录快慢指针的两个变量，空间复杂度为常数。

[leetcode]: https://leetcode.cn/problems/linked-list-cycle/description/