回文链表 LeetCode热题100

题目

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

思路

利用快慢指针找到链表中间节点，反转后半段链表。前半段从头节点开始与后半段比较。 注意当链表节点为奇数个数时中间节点不作为后半段进行翻转（可以不处理），注意快慢指针的跳出时机（快指针每跳一步都要判断是否到头了）

代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {if(head->next==nullptr){return true;}ListNode *first=head,*second = head,*pre;bool flag = false;while(first){first = first->next;if(first==nullptr){flag = true;break;}first=first->next;second = second->next;}if(flag){second = second->next;}ListNode *last=nullptr,*next;while(second){next = second->next;second->next = last;last = second;second=next;}pre = head;ListNode *revert = last;while(last){if(pre->val!=last->val){return false;}pre=pre->next;last = last->next;}return true;}
};