Two solutions in O(n) without using fast-slow pointers


  • 0
    S

    The question doesn't require keeping the list unchanged. So lets mark the visited nodes in place.
    One solution (C++, marked with null)

    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            ListNode* foo = new ListNode(-1);
            while(head!=NULL){
                if(head==foo)
                    return true;
                ListNode* tmp = head->next;
                head->next = foo;
                head = tmp;
            }
            return false;
        }
    };
    

    Another similar idea (Java, marked with self)

    public class Solution {
        public boolean hasCycle(ListNode head) {
            while(head!=null){
                if(head==head.next)
                    return true;
                ListNode next = head.next;
                head.next = head;
                head = next;
            }
            return false;
        }
    }
    

Log in to reply
 

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