Palindrome In Linked List

来源：EPI, Facebook Onsite

原帖：EPI 4.10

题目：
Write a function that determines whether a sequence represented by a singly linked list L is a palindrome. Assume L can be changed and does not have to be restored it to its original state.

代码：
1] Iteration

 // 1 -> 2 -> 2 -> 1  
 // 1 -> 2 -> 3 -> 2 -> 1  
 struct ListNode {  
     int val;  
     ListNode* next;  
     ListNode(int v) : val(v), next(NULL) {}  
 };  
   
 // Iteration  
 bool isPalindrome(ListNode* L) {  
     // Find the middle point of L  
     ListNode* slow = L, *fast = L;  
     while (fast) {  
         fast = fast->next;  
         if (fast) {  
             fast = fast->next;  
             slow = slow->next;  
         }  
     }  
     // Compare the first half and reverse second half lists  
     ListNode* reverse = reverse_linked_list(slow);  
     while (reverse && L) {  
         if (reverse->date != L->data) {  
             return false;  
         }  
         reverse = reverse->next;  
         L = L->next;  
     }  
     return true;  
 }  

2] Recursion

 bool isPalindrome(ListNode* L) {  
     ListNode* left = L, *right = L;  
     return isPalindrome(left, right);  
 }   
   
 bool isPalindrome(ListNode* &left, ListNode* right) {  
     if (!right) return true;  
     if (!isPalindrome(left, right->next)) return false;  
     if (left->val != right->next) return false;  
     left = left->next;  
     return true;  
 }