Linked List Cycle


  • 0

    Click here to see the full article post


  • 0
    D

    We should add an animation of hare and tortoise for approach #2. That would be much more fun. ^_^


  • 0
    J
    This post is deleted!

  • 0
    T

    http://cs.stackexchange.com/a/45540/41965 helped me the most to understand approach #2 in the past. I think this (or similar image) should be included here. Full article only available in archive: http://web.archive.org/web/20160323172731/http://learningarsenal.info/index.php/2015/08/24/detecting-start-of-a-loop-in-singly-linked-list/


  • 0

    @TWiStErRob Thanks for sharing the helpful link! Yes I will try to create a helpful image to accompany the explanation, thanks!


  • 0
    I

    Wow, that was a really astonishing answer for me. :) I've thought about this task for an hour and didn't make to the answer with O(1) space. Thank you for this question!


  • 0
    I

    Anyway, I wouldn't tell that it's an easy question. It's easy to solve it with HashSet, but much harder to invent the second approach by yourself if you don't know it yet. :)


  • 0

    @ivan70 You're welcome! Yes the second approach is quite neat. By the way there is another follow up to this question Linked List Cycle II, also fun to solve and is much harder.


  • 0
    R

    Nice one. I liked the second approach. Thanks for the question. :)


  • 0
    M

    "ListNode slow = head;" still allocate extra spaces. To meet the "no extra space" requirement, I just put the address of current node to next node's val:

        if (head == nullptr)
        {
            return false;
        }
        
        while (true)
        {
            if (head->next == nullptr)
            {
                return false;
            }
        
            if (head->next->val != static_cast<int>(reinterpret_cast<uintptr_t>(head)))
            {
                head->next->val = static_cast<int>(reinterpret_cast<uintptr_t>(head));
                head = head->next;
                
                continue;
            }
            
            return true;
        }

  • 0
    T

    @mazong1123 you cannot solve it without extra space. The method argument and return value is still allocating a stack entry. "No extra space" usually means O(1) space complexity. Any other space complexity than that means that the larger the input the more space you need to allocate. Your solution also destroys the list while traversing it which is not a good idea for a query function IRL.


  • 0
    S

    Nobody said we have to preserve the list, soooo ... :-| ... check if a node points to the head and if it doesn't, point it there (with a second pointer) before checking the next. The list is totally destroyed in the process, but a loop will be found!


  • 0
    T

    @semov that sounds like an O(n^2) algorithm.

    Also if I understand correctly you want to use head = head.next: this doesn't destroy the list, you just lose the reference to the beginning, but the caller will know where it starts.

    In case I misunderstood, does this handle a b c d e -> c type loops?


  • 0
    S

    @TWiStErRob what I meant was:
    For each node (after head):
    If node = head then It's a loop!!!
    NextToCheck = node.next
    Node.next = head
    Until no more next, in which case, there's no loop.


  • 0
    Y

    For some reason, the two pointers method doesn't work if the slow pointer stays at the head: I understand that moving at a +1 +2 pace means that you spot non-loops faster than the +0 +1 but why won't leetcode accept a static slow pointer?


  • -1
    S

    Well, first of all: I think the definition of a "cycle" should be given more verbose. To me, a cycle also could appear like this: 1,2,3,4,5,1,2. So, after 5, the list has a cycle. I can´t see how this case could be solved with the two-pointer-solution.


  • 0
    S

    Hey Mr. Downvoter, can you explain why you think my question is wrong?


  • 0
    Y

    @yulun It is not that incrementing the iterators at +1 +2 is faster; it is because +0 +1 increments will not work at all. Having a static slow pointer works only if the loop in the linked list includes the head (such that the whole list is part of the loop). However it will not work if the head is not part of the loop that is found further down the list. For instance, try to run your static slow pointer implementation against the following list, in which the 5th element points back at the 3rd element, such that the loop is only comprised by the 3rd, 4rd and 5th elements. It will loop forever.

    	ListNode cycled3 = new ListNode(1);
    	cycled3.next = new ListNode(2);
    	cycled3.next.next = new ListNode(3);
    	cycled3.next.next.next = new ListNode(4);
    	cycled3.next.next.next.next = new ListNode(5);
    	cycled3.next.next.next.next.next = cycled3.next.next;

  • 0
    C

    I don't think the second approch's time complexity is O(n),It's more like O(n!)


  • 0
    K

    Since there is no requirement that original list cannot be modified it is pretty easy to write even easier and faster solution which uses O(1) space and at most O(n) time :)

    public boolean hasCycle(ListNode head) {
    if (head != null) {
    ListNode fakeNode = new ListNode(-1);
    while(head.next != null) {
    ListNode next = head.next;
    if (next == fakeNode) {
    return true;
    }

                head.next = fakeNode;
                head = next;
            }
        }
        return false;
    }

Log in to reply
 

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