`

leetcode linked-list-cycle

 
阅读更多

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

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics