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;
    }