題目來(lái)源
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?
判斷單鏈表是不是回文秉版。最傻的方法就是時(shí)間復(fù)雜度O(n^2)锋华，或者空間O(n)的方法砸喻，這兩種就不說(shuō)了扁眯。O(n)時(shí)間O(1)空間的做法，怎么做呢？
感覺(jué)也是做過(guò)類(lèi)似題目的樣子。
就是找出后半段歼狼，然后反轉(zhuǎn)一下，再進(jìn)行比較享怀。
/**
* 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;
}
};
