【算法题解】环形链表（力扣141）-快慢指针

题目描述：环形链表，判断链表有无环的存在

• • • • 1. 快慢指针法

1. 快慢指针法

• 两个指针，快指针

  fast

  和慢指针

  slow

  ,
• 快指针

  fast

  每次移动两步，慢指针每次移动一步

  slow

• 遍历链表，若无环，遍历结束则快慢指针必不可能相等返回false；若有环，则快慢指针一定相等

  fast == slow

  此时返回结果true

// 快慢指针发
public boolean hasCycle(ListNode head) {
        	// base case
        	if (head == null) return false;

        	// 快指针
        	ListNode fast = head;
        	// 慢指针
        	ListNode slow = head;
        	// 移动指针到末尾
        	while (fast != null && fast.next != null) {
        		// 快指针移动两步
        		fast = fast.next.next;
        		// 慢指针移动一步
        		slow = slow.next;
                // 快指针等于慢指针，即慢指针追上来快指针（慢指针和快指针相遇了），因为有环所以相遇，
                if (fast == slow) return true;

			}
        	// 快慢指针没相遇
        	return false;

        }