leetcode-142. 环形链表 II

灰太狼学Java

发布于 2022-10-27 14:55:37

1650

发布于 2022-10-27 14:55:37

文章被收录于专栏：Java学习驿站Java学习驿站

JAVA解法（HashSet 解法）

/**
 * 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) {
        // 定义一个 HashSet 集合，利用的是 set 不可重复的性质
        HashSet<ListNode> set = new HashSet<>();
        // 新建一个节点 cur
        ListNode cur = new ListNode(0);
        // 将 cur 节点指向传进来链表的头节点 head
        cur.next = head;
        // 用 while 循环将链表上每一个不同节点都逐一加入 set 中
        while(set.add(cur) != false){
            // 若到了链表尾部，则说明不存在环
            if(cur == null){
                return null;
            }
            // 若正常则继续往下
            cur = cur.next;
        }
        // 返回起冲突的节点，此时这个节点就是环的第一个节点
        return cur;
    }
}

题解分析（HashSet 解法）

根据题目要求，我们可以想到可以利用 set 不可重复的性质来完成这道题。定义一个 HashSet 集合且新建一个节点 cur 并让 cur 指向传进来链表的头节点 head，用 while 循环将链表上每一个点都逐一加入 set 中，只要不重复且不到链表尾部，都可以正常加入 set 中，若到了链表尾部都没有冲突出现，则证明这个链表不含环，若出现冲突，则说明含环，并返回起冲突的节点，此时这个节点就是环的第一个节点。

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 fast = head;
        ListNode slow = head;
        // 在不到链表尾的情况下循环
        while (fast != null && fast.next != null) {
            // 快指针走两步，慢指针走一步
            fast = fast.next.next;
            slow = slow.next;
            // 若快指针跟慢指针相遇则说明有环
            if (fast == slow) {
                // 让快指针从头开始，每次走一步
                fast = head;
                // 当同速度的指针相遇，此时该点为环的起点，返回即可
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        // 找不到环返回空
        return null;
    }
}