LeetCode 234. 【快慢指针】【反转链表】判断回文链表
原题链接
简单
作者:
大明湖的鱼
,
2020-12-31 17:37:31
,
所有人可见
,
阅读 438
快慢指针找到中间节点,然后把后半部分逆置,逐一比较即可
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode *fast =head;
ListNode *slow = head;
while(fast){
fast = fast->next ? fast->next->next:fast->next;
slow = slow->next;
}
ListNode *prev = NULL;
while(slow){
ListNode *tmp = slow->next;
slow->next = prev;
prev= slow;
slow = tmp;
}
while(prev){//这里只需要判断prev和head其中一个就行,因为它确保了在总个数为偶数时
//分出来的两段长度是相同的,总长度为奇数的时候判断回文是不需要比较最中间的节点的,
//所以逆转后的后半段链表其实没有加入中间节点
if(head->val!= prev->val)return false;
head = head->next;
prev = prev->next;
}
return true;
}
};