回文链表

• • • • 1.题目：
      • 2.画图理解
      • 3.代码的实现

1.题目：

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

2.画图理解

链表的中间结点和反转链表实现方法之前有写过：
链表的中间结点：https://editor.csdn.net/md/?articleId=129284874
反转链表：https://editor.csdn.net/md/?articleId=129309640

3.代码的实现

//链表的中间结点：如果有两个中间结点，则返回第二个中间结点。
struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}//反转链表
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* cur=head,*newhead=NULL;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}bool isPalindrome(struct ListNode* head){//拿到链表的中间结点struct ListNode* mid = middleNode(head);//从中间结点开始逆置struct ListNode* rhead = reverseList(mid);struct ListNode* curhead = head;struct ListNode* curRhead = rhead; //当curhead 和 curRhead任意一个为空则结束while(curhead && curRhead){//curhead 和 curRhead不相等时返回falseif(curhead->val != curRhead->val){return false;}//否则curhead 和 curRhead指向nextelse{curhead=curhead->next;curRhead=curRhead->next;}}//直到curhead 或 curRhead为空还没返回false,则返回truereturn true;
}

完结~