Fast O(n) time and O(1) space solution


  • 0

    We can reverse the linked list while traversing the list. If there is a loop then we will finally reach the head where we start.

    Well, this may destroy the original list, but we can do some extra work to recover the list easily.

    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            if(!head) return false;
            ListNode* myhead = new ListNode(0);
            ListNode* prev = myhead;
            ListNode* cur = head;
            ListNode* next = 0;
            while(cur){
                next = cur->next;
                cur->next = prev;
                prev = cur;
                cur = next;
            }
            return (prev == myhead);
        }
    };
    

Log in to reply
 

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