思路二: 用兩個(gè)指針one_step,two_step,一塊向后遍歷,遍歷時(shí),one_step每次向后跳一步,two_step每次向后跳兩步,直到two_step指向NULL,說明沒有環(huán)(two_step肯定比one_step先到鏈表的尾部),或者兩個(gè)指針都沒有遍歷到NULL結(jié)點(diǎn),而兩指針指向了同一結(jié)點(diǎn),說明two_step趕上了one_step,此時(shí)肯定是有環(huán)的。
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; }
|