Linked List Cycle

文章目录

1. Linked List Cycle

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) {
        if(!head || !head->next)
            return false;
        ListNode *slow=head,*fast=head->next->next;
        while(fast and fast->next){
            if(fast==slow)
                return true;
            slow=slow->next;
            fast=fast->next->next;
        }
        return false;
    }
};

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):
        slow=head
        if not slow or not slow.next:
            return False
        fast=slow.next.next
        while fast and fast.next:
            if slow==fast:
                return True
            slow=slow.next
            fast=fast.next.next
        return False