OR36 链表的回文结构 题解

题目描述：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900

测试样例：

1->2->2->1       返回：true

题解思路：

1. 找到中间节点；
2. 在利用翻转链表的方法，将以中间节点（newList）为新的头节点来翻转链表；
3. 通过遍历比较两个链表的各个值：如果对应有一个节点的数值不相等，就返回false；如果所以节点的数值都相等，就返回ture。

代码：

struct ListNode* midNode(ListNode* head)
{struct ListNode* fast = head, *slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* n1 = NULL, *n2 = head, *n3 = head->next;while(n2 != NULL){n2->next = n1;n1 = n2;n2 = n3;if(n3 != NULL){n3 = n3->next;}}return n1;
}
bool chkPalindrome(ListNode* A) {// 找到中间节点struct ListNode* mid = midNode(A);// 翻转链表struct ListNode* newHead = reverseList(mid);// 比较struct ListNode* cur1 = A, *cur2 = newHead;while(cur1 && cur2){if(cur1->val != cur2->val){return false;}else {cur1 = cur1->next;cur2 = cur2->next;}}return true;}

 

注：

如果你还想知道回文数是如何判断的可以看一下，这一篇博客：http://t.csdn.cn/giq9u

翻转链表方法详细解释：http://t.csdn.cn/BLwnA

找链表中间节点：http://t.csdn.cn/uYTNe

---

本次内容到此结束了！如果你觉得这篇博客对你有帮助的话 ，希望你能够给我点个赞，鼓励一下我。感谢感谢……