分享

判断链表是否有环

 X的世界 2013-08-28

思路二:
用两个指针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;
}

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多