判断单链表是否有环

Sat Apr 18 17:31:18 CST 2015 635 算法

文章摘要给你一个单链表头指针,判断该链表是否有环。要求O(n)时间复杂度和常量的空间复杂度。

可以考虑采用快慢指针的算法来解决此题。设快指针为fast,慢指针为slow,fast每次走两步,slow每次走一步,若链表有环fast和slow必定相遇,若无环fast会先走到链表结尾。

java代码:

class Node{
    public int val;
    public Node next;
}

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

java

打赏
打赏

分享到: