本文主要是介绍nowcoder——回文结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
我们来分析该题：我们首先要清楚什么是回文结构？其实就是对称结构。如果一个链表呈对称结构就说明该链表具有回文结构。 下面给上一些例子：
那我们怎么判断该链表是否属于回文结构呢？
思路1：将链表元素放到数组中，然后定义两个指针分别从头部和尾部开始遍历，如果对应位置上的元素相等就说明该链表属于回文结构。这个思路虽然可以解决问题，但是题目给出了空间复杂度为O(1)的限制，所以该方法不可行。
思路2： 我们首先找到链表的中间节点，然后将中间节点之后的链表逆置，然后分别从第一个节点和逆置后的中间节点开始比较，如果对应位置上的元素相同则说明该链表符合回文结构，否则不符合。
画图表示：
有了思路，我们只需要完成第一步和第二步。找到中间节点以及逆置链表。
找链表的中间节点我在前面已经解答过了我们在这里直接CV即可。没了解过的可以看这篇博客——leetcode——链表的中间节点-CSDN博客。
逆置链表我在前面也已经解答过了我们依旧CV一下。不了解的可以看这篇——leetcode——反转链表-CSDN博客。
我们对思路进行了分析也完成了准备工作，现在我们来实现该题目：
class PalindromeList {
public://逆置链表方法ListNode* reverseList(ListNode* head){//如果原链表为空，直接返回NULLif(head == NULL){return NULL;}//原链表不为空ListNode*n1 = NULL;ListNode*n2 = head;ListNode*n3 = head->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3!=NULL){n3 = n3->next;}}return n1;}//寻找中间节点方法ListNode* middleNode(ListNode* head) {ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;}bool chkPalindrome(ListNode* A) {ListNode* mid = middleNode(A);ListNode* rev = reverseList(mid);ListNode*pcur = A;while(pcur && rev){ if(pcur->val != rev->val){return false;}pcur = pcur->next;rev = rev->next;}return true;}
};这篇关于nowcoder——回文结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
