Cycle detection in Linked List using address of nodes

Question

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.

• user3386109: Detecting a cycle in a list means looking for a next pointer in the list that points to an earlier node in the list. It has nothing to do with the memory addresses of the nodes. A linked list without a cycle would be A -> B -> C -> D -> NULL. A linked list with a cycle would be A -> B -> C -> D -> B -> ... In other words, when the list has a cycle, traversing the list will never find the end.
• Prateek Tewary: @user3386109 , I understand what cycle detection is but I am trying to implement the fact stated in the question about memory allocation in heaps. I just want to know where I am going wrong. if memory allocation in heaps actually takes place in ascending or descending manner then this code should work

Answer 1

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.

• Prateek Tewary: why will the the case of next node having less memory-address than current node emerge? If you follow memory allocation in heap then it grows in upward direction and thus every new Node added to a linked list will have greater memory address than that of the previously added node. Please clarify.
• gtristan: Apparently because it's not a strict rule that the next node address is greater than the previous, in small percentage of cases the new node gets a smaller address.

Answer 2

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 --

• Prateek Tewary: @Seam Micky, I am aware of Floyd's Tortoise And Hare Algorithm and i know that solution will work. your answer still does not answer my question. when every consequtive call to malloc() will give greater value of memory address due to memory growth in heap is upward then any next adress less that previous node's address shows that we have gone back i.e a cycle. Plz clarify my doubt.