単一チェーンテーブルの中間ノードを検索するには、チェーンテーブルを1回だけ巡回する必要があります.

質問説明:単一チェーンテーブルの中間ノードを検索するには、チェーンテーブルの実現構想を1回しか遍歴できないことが要求されています.まずチェーンテーブルを1回遍歴し、チェーンテーブルノードの個数を統計し、それから2つのヘッドノードを指すポインタを設定し、最初のチェーンテーブルの個数の半分を先に行かせ、もう1つのポインタが同じ時間に歩き始め、最初のポインタがチェーンテーブルの終わりに着いたとき、もう一つのチェーンテーブルが指すノードはチェーンテーブルの仲介ノードである.具体的なコードは以下のように実現される.

typedef int DataType;
typedef struct SListNode{
    struct SListNode* _next;
    DataType _data;
}SListNode,*pSListNode;


pSListNode FindMiddleNode(pSListNode pHead)
{
    int count = 0;
    int Mid = 0;
    pSListNode cur = pHead;
    pSListNode tmp = pHead;
    while (cur)
    {
        count++;
        cur = cur->_next;
    }
    Mid = count >> 1;
    cur = pHead;
    while (Mid--)
    {
        cur = cur->_next;
    }
    while (cur)
    {
        tmp = tmp->_next;
        cur = cur->_next;
    }
    return tmp;
}