141. 环形链表

Problem: 141. 环形链表

思路

快慢指针法,如果有环快指针一定都会在环链表中追上慢指针

解题方法

• 快指针在慢指针的前面,ListNode slow = head;ListNode fast = head.next;这样在没有进入环的时候他们不可能相遇

• 循环当 快指针 != 慢指针

    - 如果快指针或慢指针有一个为null

        - return false

    - 快指针走两步,慢指针走一步

• return true

     

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

public class Solution {

    public bool HasCycle(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;

        }

        return true;

    }

}