【LeetCode】141. Linked List Cycle

Difficulty:easy

 More:【目录】LeetCode Java实现

Description

https://leetcode.com/problems/linked-list-cycle/

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Intuition

Use two pointers at different speed: the slow pointer moves one step at a time while the faster moves two steps at a time. 

　　1) if the fast pointer meets the slow one, there is a cycle in the linked list;

　　2) if the fast pointer reaches the end(null), there is no cycle in the list.

Solution

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

Complexity

Time complexity : O(n)

Space complexity : O(1)

What I've learned

1. Have a better understanding of the use of two pointers.

  More:【目录】LeetCode Java实现