讨论/《链表》 - 环形链表/
《链表》 - 环形链表
共 22 个回复

C++

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr) return false;
        ListNode *f=head;
        ListNode *s=head;
        do{
            if(f->next==nullptr||f->next->next==nullptr) return false;
            f=f->next->next;
            s=s->next;
        }while(f!=s);
        return true;
    }
};
8

JavaScript版本~
快指针一次走两步,慢指针一次走一步,若有环存在就一定会相遇

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let fast = head
    let slow = head
    while(fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if(fast === slow) return true
    } 
    return false
};
5
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    s := head.Next
    f := head.Next.Next
    return check(s,f)
}


func check (s,f *ListNode) bool {
    if s == nil || f == nil || f.Next == nil {
        return false
    }
    if s == f {
        return true
    }
    return check(s.Next,f.Next.Next)
}
1

Java 快慢指针

public class Solution {
    public boolean hasCycle(ListNode head) {
        //快慢指针 从同一起点走
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next !=null){
            fast =fast.next.next; //快指针走两步
            slow = slow.next; //慢指针走一步
            if(slow==fast){ //快慢指针相遇,证明有环
                return true;
            }
        }
        //否则 无环
        return false;
    }
}
1
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        if(head==nullptr) return false;
        ListNode* f = head;
        ListNode* s = head;
        do
        {
            if(!f->next||!f->next->next) return false;
            f = f->next->next;
            s = s->next;
        }while(f!=s);
        return true;
    }
};

Java版,注意判断空指针就ok

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode temp;
        while (true) {
            slow = slow.next;
            temp = fast.next;
            if (temp == null) {
                return false;
            }
            fast = temp.next;
            if (fast == null) {
                return false;
            }
            if (slow == fast) {
                return true;
            }
        }
    }
}

res.jpg

TypeScript 版本

function hasCycle(head: ListNode | null): boolean {
    let fast = head
    let slow = head

    while(fast?.next) {
        fast = fast.next?.next
        slow = slow?.next
        if(fast === slow) {
            return true
        }
    }

    return false
};

//优化1:慢指针不用判断,因为快指针还在动,慢指针肯定没有到达。
//优化2:快指针只要有null,就停止,因为有null代表非环路.

龟兔赛跑:如果兔子再次和乌龟相遇(有环),返回 true;否则,返回false。
C 语言:

bool hasCycle(struct ListNode *head) {
    struct ListNode *p = head, *q = head;
    while(p && q && q->next){
        p = p->next;
        q = q->next->next;
        if(p == q){
           return true;
        }
    }
    return false;
}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *cur = head;
        while(cur){
            if(cur->val == 100001){
                return true;
            }else{
                cur->val = 100001;
            }
            cur = cur->next;
        }
       return false;
    }
};

每次访问结点标记下就好,
下次遇到表示肯定有环,直接返回
如果没用。就返回false
题目val范围100000,我们设置100001就可以了