給定一個鏈表，判斷該鏈表是否為回文結構。回文是指該字符串正序逆序完全一致。如當輸入鏈表 {1,2,3,2,1} 時，斷定是回文結構，輸出True。

代碼實現

C語言代碼：

boolisPail(structListNode*head){
//writecodehere
if(head==NULL||head->next==NULL)
returntrue;
//第一步：定義快慢指針，并將其指向頭結點
structListNode*slow,*fast;
slow=head;
fast=head;
//第二步：快指針每次走兩步，慢指針走一步
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
}
//第三步：快指針指向慢指針后繼結點，慢指針斷鏈
fast=slow->next;
slow->next=NULL;

structListNode*p;
p=NULL;
//第四步：反轉后半部分的鏈表
while(fast!=NULL){
p=fast->next;
fast->next=slow;
slow=fast;
fast=p;
}
//第五步：將快指針指向原始鏈表頭部，將快慢指針結點的值進行對比
fast=head;
while(fast!=NULL&&slow!=NULL){
if(fast->val!=slow->val)
returnfalse;
fast=fast->next;
slow=slow->next;
}
returntrue;
}

圖解代碼

第一步：定義快慢指針，并將其指向頭結點

第二步：快指針每次走兩步，慢指針走一步

第三步：快指針指向慢指針后繼結點，慢指針斷鏈

第四步：反轉后半部分的鏈表

第五步：將快指針指向原始鏈表頭部，將快慢指針結點的值進行對比

分享、在看與點贊

只要你點，我們就是胖友

原文標題：數據結構：判斷鏈表回文結構

文章出處：【微信公眾號：嵌入式攻城獅】歡迎添加關注！文章轉載請注明出處。