思路二: 用两个指针one_step,two_step,一块向后遍历,遍历时,one_step每次向后跳一步,two_step每次向后跳两步,直到two_step指向NULL,说明没有环(two_step肯定比one_step先到链表的尾部),或者两个指针都没有遍历到NULL结点,而两指针指向了同一结点,说明two_step赶上了one_step,此时肯定是有环的。
int is_cycle_list(Node *list) { Node *one_step, *two_step; one_step = two_step = list; if(!list) { return FALSE; } while(two_step) { one_step = one_step->next; two_step = two_step->next; if(!two_step) { return FALSE; } two_step = two_step->next; if(one_step == two_step) { return TRUE; } } return FALSE; }
|