一.前言

今天在牛客網上刷到了一道鏈表題——鏈表的回文結構https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?，巧合的是它的解題思路恰好是我們一起分享過兩道鏈表題的匯總。這兩道題分別是反轉鏈表和鏈表的中間節點。廢話不多數，讓我們直接進入今天的正文環節吧。

二.正文

1.1題目描述

1.2題目分析

對于這道題，我們的思路是先找到鏈表的中間節點，然后將中間節點及之后的鏈表進行逆置，這樣就可以得到兩個鏈表的頭節點。并讓這兩個鏈表的元素依次比較大小，如果元素依次相同，則返回true，否者返回false。

就比如：1->2->2->1

對于反轉鏈表和找到中間節點可以看我寫的文章。下面是對應其鏈接：

反轉鏈表：https://blog.csdn.net/yiqingaa/article/details/138376042?

查找中間節點：https://leetcode.cn/problems/middle-of-the-linked-list

1.3代碼實現

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/typedef struct ListNode ListNode;
class PalindromeList {
public:
ListNode* middleNode(struct ListNode* head) 
{ListNode* slow;ListNode* fast;fast=slow=head;while((fast!=NULL)&&(fast->next!=NULL)){slow=slow->next;fast=fast->next->next;}return slow;
}
typedef struct ListNode ListNode;
ListNode* ReverseList( ListNode* head)
{
// if(head==NULL)//  return NULL;ListNode*pcur,*prev,*pnext;ListNode* phead=(ListNode*)malloc(sizeof(ListNode));phead->next=head;pcur=head;prev=phead;pnext=pcur->next;while(pcur!=NULL){pcur->next=prev;prev=pcur;pcur=pnext;if(pnext!=NULL)pnext=pnext->next;}head->next=NULL;free(phead);phead=NULL;return prev;
}bool chkPalindrome(ListNode* A) {// write code here
ListNode* mid=middleNode(A);
ListNode* remid= ReverseList(mid);
while(remid&&A)
{if(A->val!=remid->val)return false;else{A=A->next;remid=remid->next;}}
return true;} 
};

值得注意的是，以上代碼是在牛客網上運行的。

三.結言

今天的題目就分享到這了，帥哥美女們，我們下次再見嘍，拜拜~