Easiest solution guaranteed (With space: O(1) time: O(n))


  • 0
    W

    The idea is basically linking all the node visited to the head of the original linkedlist. If during the traversal there exist a node with its next pointed to the head, then this linkedlist must have been visited before, which implies that the linkedlist has a cycle.

    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            if (!head) return false;
            ListNode* tmpnode = head;
            ListNode* node = head;
            while (node) {   
                if (node->next == tmpnode) {
                    return true;
                }
                head = node;
                node = head->next; 
                head->next = tmpnode;
            }
            return false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.