C言語回文チェーン表

1852 ワード

要求:チェーンテーブルが返信チェーンテーブルであるかどうかを判断してください.
例1:

  : 1->2
  : false

例2:

  : 1->2->2->1
  : true
  ：       +     +      
  ：              。         1->1->2->1->1->NULL  slow    2，fast       1，   2       prev  1，
          slow   1 ，    while(prev!=NULL)  。

bool isPalindrome(struct ListNode* head){
//特別な事情を排除する
if(head == NULL||head->next==NULL)
return true ;
if(head->next->next==NULL)
{
    if(head->val==head->next->val)
    return true ;
    else
    return false ;
}
//スローツーポインタを定義します.クイックポインタが移動したとき、スローポインタがチェーンテーブルの真ん中を指します.
struct ListNode* slowp=head->next ;//グリッドを移動するたびに
struct ListNode* fastp=head->next->next ;//毎回2つのグリッドを移動
while(fastp!=NULL && fastp->next!=NULL)
{
    slowp=slowp->next ;
    fastp=fastp->next->next;
}
//その後、中央部の前のチェーンテーブルを反転して、後続の比較を容易にする
struct ListNode* prev =NULL ;
struct ListNode* Temp =NULL ;
struct ListNode* curr =head;
//反転
while(curr!=slowp)
{
    Temp =curr->next ;
    curr->next =prev ;
    prev = curr ;
    curr = Temp ;
}
//奇数個の場合は真ん中のslowと比較する必要がないので1マス後ろに移動
  if(fastp !=NULL && fastp->next==NULL)
{
    slowp=slowp->next ;
}
//返信照合
    while(prev!=NULL)
    {
        if(prev->val != slowp->val)
        return false ;
        prev=prev->next;
        slowp=slowp->next;
    }
    return true;

}

MergeList

チェーンテーブルの学習と認識