チェーンテーブルがエコー構造であるかどうかを判断する(時間、空間の複雑さに要求がある)

タイトル:チェーンテーブルについて、時間複雑度O(n)、余分な空間複雑度O(1)のアルゴリズムを設計し、それが回文構造であるかどうかを判断してください.
チェーンテーブルのヘッダポインタAを指定します.bool値を返します.これは、エコー構造であるかどうかを表します.チェーンテーブルの長さが900以下であることを保証します.
試験例:1->2->2->1
戻る:true
ポイント:1.返信構造を判断する方法
           2. 時間、空間の複雑さを満たすアルゴリズムを設計する(難点)
知識点:1.高速ポインタを使用して中間ノードを見つけます.
              2.チェーンテーブルを反転します.
構想1:空間O(n)全体のチェーンテーブルは両側を遍歴して、1つのスタックを開いて、第1回の遍歴はチェーンテーブルの中の各要素pushをスタックの中に入れて、このようにスタックの中の要素のpopの順序はチェーンテーブルの逆順序の出力です;2回目はpopスタックのデータを開始し、popごとに1つのデータをチェーンテーブルと比較し、同じように下に進むとfalseに戻ります.
この場合,時間的複雑度はO(n),空間的複雑度はO(n)である.

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        if(A==NULL)   return true;
        ListNode* B;
        stack s;
        B=A;
      
        while(B!=NULL)
            {
             s.push(B->val);
             B=B->next;
        }
        
        while(A!=NULL && !s.empty())
            {
            if(A->val==s.top())
                {
                A=A->next;
                s.pop();
            }
            else return false;
        }
       return true;
        // write code here
    }
};

考え方2:空間O(1)
(1)クイックスローポインタ法を用いて,最初のステップにブロックポインタとスローポインタを設定し,クイックポインタは1回に2歩,スローポインタは1回に1歩(スロー)歩き,クイックポインタが次のステップにnullのときにスローポインタが半分歩いたことを説明し,中間ノードを見つけることができる.
(2)第2のステップで中間チェーンテーブルの後ろのポインタを反転し、
(3)第3部は,各要素が等しいか否かを比較し,等しい場合は回文数,そうでない場合は回文数である.(以下、易水さんはコード実装を示していますが、ここでは説明しません)

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        if(A==NULL)   return true;
        ListNode* mid;
        ListNode* fast;
        ListNode* temp;
       
            mid=A;
            fast=A;
      
        while(fast->next!=NULL)
             {
             temp=mid;   //temp      mid       
             mid=mid->next;
             fast=fast->next;
            if(fast->next!=NULL)
                fast=fast->next;   //     ，         ，mid       ，         ，mid              。
        }
        if(mid==A)   return true;  //       1 ，       ；
        ListNode* cur;

        temp->next=NULL;     //temp     ，  temp      
        cur=mid->next;
        mid->next=NULL;
        while(cur!=NULL)
            {
            temp=cur->next;      //mid，cur，temp          。
            cur->next=mid;
            mid=cur;
            cur=temp;
        }
        
        while(A!=NULL && mid!=NULL)
            {
            if(A->val==mid->val)
                {
                A=A->next;
                mid=mid->next;
            }
            else return false;
        }
       return true;
        // write code here
    }
};

注意ここでは、要素の数が2の場合を含み、midとfastは2番目の要素を指します.

while(fast->next!=NULL)
             {
             temp=mid;   //temp      mid       
             mid=mid->next;
             fast=fast->next;
            if(fast->next!=NULL)
                fast=fast->next;   //     ，         ，mid       ，         ，mid              。
        }

は簡単には書けません.この場合、要素の個数が1と2の特殊な状況は無視されます.

while(fast->next->next!=NULL)
{
    mid=mid->next;
    fast=fast->next->next;
}