チェーンテーブル(9)----チェーンテーブルにリングがあるかどうかを判断する

1、チェーンテーブル定義

typedef struct ListElement_t_ {
    void *data;
    struct ListElement_t_ *next;
} ListElement_t;


typedef struct List_t_{
    int size;
    int capacity;
    ListElement_t *head;
    ListElement_t *tail;
} List_t;

2、チェーンテーブルにループがあるかどうかを判断するには、2つのポインタを使用して、速いポインタは一度に2つのノードを歩いて、遅いポインタは一度に1つのノードを歩いて、出会ったらループがあることを示して、さもなくばループがありません.

bool   CheckCircle( List_t *list){
    //      ，     
    if ( list == NULL || list->head == NULL || list->head->next == NULL )
        return false;

    ListElement_t *pFast = list->head;
    ListElement_t *pSlow = list->head;
    while( pFast->next != NULL && pFast->next->next != NULL ){
        pFast = pFast->next->next;
        pSlow = pSlow->next;
        if( pFast == pSlow )
            return true;
    }

    return false;
}

その他の関連トピックは、次のハイパーリンク形式で表示されます.
チェーンテーブル面接問題集
1、単一チェーンテーブルの基本操作
2、ダブルチェーンテーブルの基本操作
3、循環単鎖表の基本操作
4、単一チェーンテーブルの反転
5、単一チェーンテーブルの最後からK番目のノードを検索する
6、チェーンテーブルの逆順序印刷
7、チェーンテーブルの中間ノードを探す
8、チェーンテーブルK番目のノードを削除し、平均時間複雑度はO(1)
9、チェーンテーブルにリングがあるかどうかを判断する
10、2つのチェーンテーブルが交差しているかどうかを判断する
11、交差チェーンテーブルの最初の交差ノードを求める
12、リングがあるかどうかを判断し、6型リングか0型リングかを判定する
13、チェーンテーブルにリングがあるかどうかを判断し、リング入口ノードを求める
14.2つの順序付き単一チェーンテーブルを結合する
15、所与のチェーンテーブルの中にあるノードはチェーンテーブルを遍歴せず、バンド挿入ノードを所与のノードの前に挿入する
16、チェーンテーブル重複要素の削除