The idea is not so obvious at first glance. Since you cannot move from a node back to its previous node in a singly linked list, we choose to reverse the right half of the list and then compare it with the left half. The code is as follows. It shoul be obvious after you run some examples.
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 bool isPalindrome(ListNode* head) { 12 if (!head || !(head -> next)) return true; 13 ListNode* slow = head; 14 ListNode* fast = head; 15 while (fast && fast -> next) { 16 slow = slow -> next; 17 fast = fast -> next -> next; 18 } 19 if (fast) { 20 slow -> next = reverseList(slow -> next); 21 slow = slow -> next; 22 } 23 else slow = reverseList(slow); 24 while (slow) { 25 if (head -> val != slow -> val) 26 return false; 27 head = head -> next; 28 slow = slow -> next; 29 } 30 return true; 31 } 32 private: 33 ListNode* reverseList(ListNode* node) { 34 ListNode* pre = NULL; 35 while (node) { 36 ListNode* next = node -> next; 37 node -> next = pre; 38 pre = node; 39 node = next; 40 } 41 return pre; 42 } 43 };
