如何判断[牛客]链表是否具有回文结构？

本文共计354个文字，预计阅读时间需要2分钟。

牛客链表+思路：找到中间节点+从中间节点开始对后半段进行逆置+比较前半段和后半段+相等的是，不相等则不是+只需将我们前面写过的链表中间节点逆置代码、逆置链表的代码复用，并加上如下代码即可：

牛客链接

思路:

找中间结点

从中间结点开始对后半段进行逆置

比较前半段和后半段

相等是,不相等不是

只需将我们前面写过的链表中间结点,逆置链表的代码复用,并加上如下代码即可

最终代码:

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: //返回中间结点 struct ListNode* middleNode(struct ListNode* head){ struct ListNode*slow,*fast; slow = fast = head; while(fast && fast->next)//考虑到结点个数的奇 { slow = slow->next; fast= fast->next->next; } return slow; } //链表逆置 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur,*newHead; cur = head; newHead = NULL; while(cur) { struct ListNode* next = cur->next; cur->next = newHead; newHead = cur; cur = next; } return newHead; } bool chkPalindrome(ListNode* head) { struct ListNode* mid = middleNode(head); struct ListNode* rhead = reverseList(mid); while(head && rhead) { if(head->val != rhead->val) return false; head = head->next; rhead = rhead->next; } return true; } };