leetcode linked-list-cycle

141. Linked List Cycle

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

分析：

有两种解决办法：

1，采用一个set集合，遍历listnode，如果没有包含，就add，如果有，就说明曾经遍历过，返回true

时间复杂度o(n)

空间复杂度o(n)

代码：

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

 2，采用龟兔赛跑的概念，乌龟一次跑一步，兔子一次跑两步，如果乌龟和兔子遇见过，说明存在环，如果没有，则表示没有

时间复杂度o(n)

空间复杂度o(1)

代码如下：

public  static boolean hasCycle(ListNode head){
        if(head.next==null) return false;
        ListNode first = head; // 乌龟，一次跳一个
        ListNode second = head; // 兔子，一次跳两个
        while(second!=null&&second.next!=null){
               first=first.next;
               second=second.next.next;
            if (first==second){
                return true;
            }

        }
        return false;
    }