力扣热题100-环形链表_java 力扣100题

原题链接：环形链表

题目：给定一个链表的头节点，判断该链表是否有环

解法一：HashSet集合去重

1. 遍历链表节点
2. 将链表每一个节点以此加入HashSet中
3. 当set.add(ListNode)返回false时，代表当前节点重复
4. 依次执行2，3步，直到链表到达尾节点

代码：

public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null){
            if (!set.add(head)){
                return true;
            }
            head = head.next;
        }
        return false;
    }

解法二：快慢指针

1. 定义两个节点作为指针，分别指向头节点以及头节点的下一节点
2. 慢指针每次走一步(即指向当前节点的下一个节点)，快指针每次走两步(即指向当前节点的下下一个节点)
3. 当两指针指向同一节点时代表链表存在环(即慢指针追上快指针)
4. 遍历到若快指针到达尾节点则链表无环

如上图，快慢指针slow，fast分别指向head，head.next节点，若慢指针追上快指针，则证明该链表存在环

代码：

public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null){
            if (slow == fast) return true;
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

---

进一步找出环形链表中环开始的第一个节点？

原题链接：环形链表环开始的节点

解法一：HashSet集合去重

1. 遍历链表节点
2. 将链表每一个节点以此加入HashSet中
3. 当set.add(ListNode)返回false时，代表当前节点重复且为环开始的节点
4. 依次执行2，3步，直到链表到达尾节点

代码：

public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null){
            if (!set.add(head)){
                return head;
            }
            head = head.next;
        }
        return null;
    }

解法二：快慢指针

1. 定义两个节点作为指针，分别指向头节点以及头节点的下一节点
2. 慢指针每次走一步(即指向当前节点的下一个节点)，快指针每次走两步(即指向当前节点的下下一个节点)
3. 当两指针第一次相遇时即代表该链表存在环，此时使慢指针指向头节点，快指针指向当前节点下一节点
4. 之后两指针同时移动一个节点，当两节点下次相遇时，此节点即为该链表环的开始节点
5. 遍历到若快指针到达尾节点则链表无环

如上图，当慢指针，快指针slow，fast第一次在b节点相遇，此时slow指向head指针，fast指向下一节点，下一次相遇时即为a节点

两指针在b节点相遇则代表head到b节点的距离等于b节点绕环一圈到b节点距离，两段距离同时减去a到b的距离即相等，即head到a节点距离等于b到a节点距离，即快慢指针此时速度相同则可同时到达a节点

总结：

1. 首先链表存在环是指节点重复，并非节点值重复
2. HashSet去重需要计算hash值并存储等等，时间复杂度会更高
3. 环形链表适合使用快慢指针解决