
- 用快慢指针找到链表中间节点
- 反转后面一段链表
- 遍历每个节点做判断
- 为什么是while pre: 不能写while head呢 ?
答:因为slow节点在反转后,他的前序节点除了反转之后的节点,之前正序的节点仍然存在的,即slow.pre 的next依旧是slow, 我们在逻辑中并没有断开,所以head到None的长度永远是大于等于prev到None的长度,如果使用while head 会发现错误。
class Solution {
public:bool isPalindrome(ListNode* head) {ListNode* slow = head;ListNode* fast = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;}ListNode* prev = NULL;while(slow){ListNode* next = slow->next;slow->next = prev;prev = slow;slow = next;}while(prev){if(prev->val!=head->val) return false;prev = prev->next;head = head->next;}return true;}
};