Original title: How can I detect that there is a loop in the list (from "c expert programming")
answer:
Condition: There is no condition. Method: For each element accessed, it is a tag, traversing the entire linked list. When you encounter a marked element for the first time, you find the start node of the ring.
Condition: The linked list exists in read-only storage, not marking. Method: Place the checked node pointer into an array, and look up in the table each time you check the new node pointer, see if there is the same node. If present, the node is the start node of the ring. So usually practices can use hash tables and haveh functions to store the check nodes and check nodes, and the focus is also available.
Condition: The length of the linked list is arbitrary and the cycle may also appear anywhere. Method: First, a special case is excluded, it is the first element of the second element in the linked list of three elements. Set two pointers P1 and P2, P1 point to the first element, P2 points to the third element to see if they are equal. If equally belongs to the above special case. If not, the P1 is moved backwards, and the P2 is moved backwards two elements. Check the value of the two pointers, if equally, explain the loop in the linked list. If it is not equal, continue in accordance with the foregoing method. If a pointer appears is NULL, there is no loop in the linked list. If there is a loop in the linked list, this method must be able to detect because one of the pointers in the single-linked list must be able to catch up with another (two pointers have the same value). However, this method may need to traverse the linked list several times to detect.
