首页 > 代码库 > 【LeetCode】Linked List Cycle

【LeetCode】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?


     思路:

     如何判断一个链表存在环?可以设置两个指针,一个快,一个慢,沿着链表走,在无环的情况下,快指针很快到达终点。如果存在环,那么,快指针就会陷入绕圈,而最后被慢指针追上。


     代码:

     C++:

/**
 * 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) {
        /*初始都指向 head */
        ListNode *pfast = head,*pslow = head;
        do{
            /*快指针两倍速*/
            if(pfast != NULL) pfast = pfast->next;
            if(pfast != NULL) pfast = pfast->next;

            /*到达 null,无环 */
            if(pfast == NULL) return false;

            /*慢指针*/
            pslow = pslow->next;
        }while(pfast != pslow);
        return true;
    }
};

     Python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a boolean
    def hasCycle(self, head):
        
        pfast = head
        pslow = head
        
        while True:
            if pfast != None:
                pfast = pfast.next
            if pfast != None:
                pfast = pfast.next
            
            if pfast == None:
                return False
            
            pslow = pslow.next
            
            if pfast == pslow:
                break
        
        return True
        


【LeetCode】Linked List Cycle