LeetCode 142. 环形链表 II

谁借莪１个温暖的怀抱￠ 2022-11-03 11:52 188阅读 0赞

### LeetCode 142. 环形链表 II ###

*  题目：
 *  解题方法：
 *   *  方法1：哈希表法
     *   *  Java实现
     *  方法2：快慢指针法（空间复杂度是O(1)）
     *   *  Java实现

# 题目： #

[LeetCode 142. 环形链表 II][LeetCode 142. _ II]

> 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
> 
> 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
> 
> 说明：不允许修改给定的链表。

进阶：

> 你能用 O(1)（即，常量）内存解决此问题吗？

> 提示：  
> 链表中节点的数目范围是 \[0, 104\]  
> \-105 <= Node.val <= 105  
> pos 为 -1 或者链表中的一个 有效索引 。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Blbmd4aWFvemhlbjExMTE_size_16_color_FFFFFF_t_70]

# 解题方法： #

## 方法1：哈希表法 ##

思路：这里我们用Java 的HashSet数据结构。遍历一遍元素，没有遍历过就存进哈希表中，如果存在add() 方法会返回false。当有元素add 返回false时，就证明是成环了, 返回当前节点。否则遍历完整个链表，返回null。

### 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) {
            HashSet<ListNode> hashSet = new HashSet<>();
            while (head != null) {
                if (!hashSet.add(head)) {
                    return head;
                }
                head =  head.next;
            }
            return null;
        }
    }

**复杂度分析**：  
时间复杂度：O(N)，其中N是链表中的节点数。最坏情况下首尾成环，需要每个元素遍历N次。  
空间复杂度：O(N)，其中N是链表中的节点数。这里主要是HashSet存储元素的空间，最坏情况每个元素都需要存储进去。

## 方法2：快慢指针法（空间复杂度是O(1)） ##

### Java实现 ###

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (fast == slow) {
                    ListNode slow2 = head;
                    while (slow2 != slow) {
                        slow2 = slow2.next;
                        slow = slow.next;
                    }
                    return slow2;
                }
    
            }
            return null;
        }
    }

**复杂度分析**：  
时间复杂度：O(N)，其中N是链表中的节点数。最坏情况下首尾成环，需要每个元素遍历N次。  
空间复杂度：O( 1)，只使用了常数个指针作为额外的空间。

[LeetCode 142. _ II]: https://leetcode-cn.com/problems/linked-list-cycle-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Blbmd4aWFvemhlbjExMTE_size_16_color_FFFFFF_t_70]: /images/20221024/933feec58bb348a7959b48ed35383186.png