题目来源
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
判断单链表是不是回文。最傻的方法就是时间复杂度O(n^2)，或者空间O(n)的方法，这两种就不说了。O(n)时间O(1)空间的做法，怎么做呢？
感觉也是做过类似题目的样子。
就是找出后半段，然后反转一下，再进行比较。
/**
* 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) {
if (!head || !head->next)
return true;
ListNode *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next;
fast = fast->next;
}
ListNode *head2 = slow->next;
head2 = reverseList(head2);
while (head2) {
if (head->val != head2->val)
return false;
head = head->next;
head2 = head2->next;
}
return true;
}
ListNode* reverseList(ListNode *node)
{
ListNode *next = node->next;
ListNode *pre = NULL;
while (node) {
node->next = pre;
pre = node;
node = next;
if (node)
next = node->next;
}
return pre;
}
};
