牛客|牛客OR36 .链表的回文结构链表|数据结构|算法|牛客OR36

对于一个链表，请设计一个时间复杂度为O(n), 额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
思路1：
找到链表的中间结点，然后拆开链表，分成两部分，将后半部分逆置，后半部分和前部分比较是否相等，只要有一个走到NULL了，就结束
（1）偶数个

文章图片

文章图片

文章图片

（2）奇数个

文章图片

文章图片

文章图片

这种方法，要把链表拆开
思路2：
不拆链表
（1）偶数个
找到中间结点，

文章图片

中间结点后的部分逆置，不要拆开

文章图片

（2）奇数个

文章图片

struct ListNode { int val; struct ListNode* next; }; bool chkPalindrome(struct ListNode* A) { //1.先找到中间结点 - 快慢指针 struct ListNode* slow = A; struct ListNode* fast = A; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } //此时slow就是中间结点//逆置后半部分 struct ListNode* n1 = NULL; struct ListNode* n2 = slow; struct ListNode* n3 = slow->next; while (n2 != NULL) { n2->next = n1; n1 = n2; n2 = n3; if (n3 != NULL) { n3 = n3->next; } }//比较前半部分和后半部分 struct ListNode* cur1 = A; struct ListNode* cur2 = n1; while (cur1 != NULL && cur2 != NULL) { if (cur1->val == cur2->val) { //继续 cur1 = cur1->next; cur2 = cur2->next; } else { return 0; } }return 1; }

【牛客|牛客OR36 .链表的回文结构】找中间结点、链表逆置可以封装成函数。

struct ListNode* reverseList(struct ListNode* head) { if (head == NULL) { return NULL; }struct ListNode* n1 = NULL; struct ListNode* n2 = head; struct ListNode* n3 = head->next; while (n2 != NULL) { //翻转 n2->next = n1; //继续向后走 n1 = n2; n2 = n3; if (n3 != NULL) { n3 = n3->next; } } return n1; }struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }bool chkPalindrome(struct ListNode* A) { struct ListNode*slow = middleNode(A); //此时slow就是中间结点//逆置后半部分 struct ListNode* newHead = reverseList(slow); //比较前半部分和后半部分 struct ListNode* cur1 = A; struct ListNode* cur2 = newHead; while (cur1 != NULL && cur2 != NULL) { if (cur1->val == cur2->val) { //继续 cur1 = cur1->next; cur2 = cur2->next; } else { return 0; } }return 1; }