給定一個(gè)鏈表，判斷該鏈表是否為回文結(jié)構(gòu)?；匚氖侵冈撟址蚰嫘蛲耆恢?。如當(dāng)輸入鏈表 {1,2,3,2,1} 時(shí)，斷定是回文結(jié)構(gòu)，輸出True。

代碼實(shí)現(xiàn)

C語言代碼：

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

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

圖解代碼

第一步：定義快慢指針，并將其指向頭結(jié)點(diǎn)

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

第三步：快指針指向慢指針后繼結(jié)點(diǎn)，慢指針斷鏈

第四步：反轉(zhuǎn)后半部分的鏈表

第五步：將快指針指向原始鏈表頭部，將快慢指針結(jié)點(diǎn)的值進(jìn)行對(duì)比

分享、在看與點(diǎn)贊

只要你點(diǎn)，我們就是胖友

原文標(biāo)題：數(shù)據(jù)結(jié)構(gòu)：判斷鏈表回文結(jié)構(gòu)

文章出處：【微信公眾號(hào)：嵌入式攻城獅】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。