234-回文链表

本文主要是介绍234-回文链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：

输入：head = [1,2,2,1]
输出：true
示例 2：

输入：head = [1,2]
输出：false

思路

快慢指针,找到中点;
前一半链表反转,方法三指针遍历或者递归
前后对比.

C++代码

class Solution {
private:ListNode* reverse(ListNode* head,ListNode* slow){if(head==slow)return slow;ListNode* res =  reverse(head->next,slow);head->next->next = head;head->next = nullptr;return res;}
public:bool isPalindrome(ListNode* head) {ListNode* fast=head;ListNode* slow=head;while(fast->next!= nullptr&&fast->next->next!= nullptr){fast=fast->next->next;slow=slow->next;}ListNode* half = slow->next;ListNode *res = reverse(head, slow);if (fast->next == nullptr)slow = slow->next;while (half != nullptr) {if (half->val != slow->val)//注意这里是val,回文是val相等,不是地址相等return false;half = half->next;slow = slow->next;}return true;}
};

这篇关于234-回文链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---