CODEWITHSUNDEEP
cdata-structureslinked-listheap-memorycycle-detection
Prateek Tewary
Prateek Tewary

Reputation: 33

Cycle detection in Linked List using address of nodes

I have learned recently that:

(typically)heap in memory always grows upward

refer to-> https://unix.stackexchange.com/questions/466443/do-memory-mapping-segment-and-heap-grow-until-they-meet-each-other
I didn't understand most of it but when I searched for whether heap grows upwards in memory then I got similar results.

Considering the above fact in c/c++, I have written a function checking for cycle detection where if the traversing pointer to structure temp points to a memory address less than the memory address of previous node in the linked list then the function returns TRUE for cycle detection.

Unfortunately the below code is not giving desired results on hackerrank and I want to know why. The code is: 

bool has_cycle(SinglyLinkedListNode* head) {
    struct SinglyLinkedListNode* temp = head;
    int x;
    if( temp == NULL )
    return false;             //FALSE indicates No cycle detected in linked list

    if( temp->next == NULL )
    return false;

    x = temp;
    while( temp->next != NULL )
    {
        temp = temp->next;
        if( x >= temp )
        return true;          //TRUE indicates Cycle detected in linked list

        x= temp;
    }

    return false;

}

I have checked for the condition if the memory allocation in heap is downwards if( x <= temp ) (descending order) as memory allocation is device/compiler specific but that too didn't work. I want to know as to why this code is not working and what conceptual errors this code posseses.

Upvotes: 0

Views: 497

Answers (2)

Sean Mickey
Sean Mickey

Reputation: 7716

I have to agree with @gtristan. I can't see where the memory address comparisons will lead to a definitive cycle detection solution. The general two-node approach is an accepted solution and works well. Take a look at these two related cycle-detection algorithms: Floyd's Tortoise And Hare Algorithm and Brent's Telescoping Turtle Algorithm. I recently implemented Floyd's algorithm in Java (nothing fancy code below) on HackerRank and this ran clean across all test cases:

// Complete the hasCycle function below.
/*
 * For your reference:
 *
 * SinglyLinkedListNode {
 *     int data;
 *     SinglyLinkedListNode next;
 * }
 *
 */
static boolean hasCycle(SinglyLinkedListNode head) {
    if (head == null) { return false; }
    SinglyLinkedListNode slow = head, fast = head;
    while (slow.next != null) {
        slow = slow.next;
        if (fast.next != null) {
            fast = fast.next;
            if (fast.next != null) {
                fast = fast.next;
                if (fast == slow) {
                    return true;
                }
            }
        }
    }
    return false;
}

Hope this helps --

Upvotes: 0

gtristan
gtristan

Reputation: 445

If you create a linked list with several thousands elements and try to calculate how many times the address of the next list is smaller than of the current, you'll get a few, so this approach to find weather there is a cycle won't work. The correct approach would be to make two pointers, one of which will move one list at a time and the other will move two lists at a time and checking each move if the address of these two pointers is the same.

Upvotes: 1

Related Questions