LC0141-环形链表---LC0142-环形链表 II

141. 环形链表

​​关于链表的小总结​​

利用集合存放数据,不在就就存放数据,进行遍历

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

利用快慢指针

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

package com.nie.FFHanjia.day1;/*
 *
 *@auth  wenzhao
 *@date 2021/1/30  16:31
 */

public class LEE141 {

    public boolean hasCycle(ListNode head) {

        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (true) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) return true;
        }

    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}      

​​142. 环形链表 II​​

利用集合进行普通的遍历

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

            }
            head = head.next;
        }
        return null;
    }      

快慢指针进行遍历

​​具体详解看​​

根据：

1. f=2s （快指针每次2步，路程刚好2倍）
2. f = s + nb (相遇时，刚好多走了n圈）

推出：s = nb

从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。

public ListNode detectCycle2(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (true) {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }