Question

You are given a pointer head to the first node in a linked list. Each node points to the next node. We call the list a snail if the last node points to some node v in the list. We call the list a snake if the last node points to NULL. The list has n nodes. You are not allowed to change the list (permanently or temperately). You are allowed to use O(1) extra memory. The value of n is not known to you.

Suggest an algorithm that the pointer to the first node, and after O(n) time and identify if the list is a snake or a snail.

please be detailed in response thanks!

Answer 1

1. START
2. READ pointer HEAD
3. set ptr= HEAD
4. Repeat steps 5- 9 until ptr->next!=NULL OR ptr->NEXT!= HEAD
5. if ptr->next== NULL execute steps 6
6. Set type=snake
7. if ptr->next== HEAD
8. Set type=snail
9. ptr=ptr->next
10. DISPLAY type
11. STOP

The control keep on traversing until it encounters a NULL or HEAD values. If it encounters a NULL value then its a snake. If it encounters a Head value then its snail type.