234. Palindrome Linked List

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?

idea: Firstly find the middle node in the linked list using the slow and fast pointer, then reverse the second half of the linked list after the middle node and compare it to the first half. Note the condition that the list has none or one node(line 6). Here we use three ListNode pointer pre,cur and temp to reverse the list.

 1 class Solution {
 2 public:
 3     bool isPalindrome(ListNode* head) {
 4         ListNode* slow=head;
 5         ListNode* fast=head;
 6         if (!head || !head->next) return true;
 7         //find the middle node in the linked list using the slow and fast pointer
 8         while(fast->next && fast->next->next){   
 9             slow=slow->next;
10             fast=fast->next->next;
11         }
12         ListNode* pre=slow->next;
13         ListNode* cur=pre->next;
14         pre->next=NULL;
15         while(cur!=NULL){
16             ListNode* temp=cur->next;
17             cur->next=pre;
18             pre=cur;
19             cur=temp;
20         }
21         slow->next=pre;
22         while(pre!=NULL){
23             if (pre->val!=head->val) return false;
24             pre=pre->next;
25             head=head->next;
26         }
27         return true;
28     }
29 };