234. Palindrome Linked List

I count the total nodes first and then find the middle node. To cover both cases of odd/even number, the middle node should be the ceiling of n / 2. And then reverse the sublist starting from the middle node. After that, compare the first half list with the reversed second half list to see if any discrepancy.

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:      int count = countList(head);  
13:      if (count < 2) return true;  
14:      int mid = (count+1)/2;  
15:      ListNode *l2 = head;  
16:      while (mid) {  
17:        l2 = l2->next;  
18:        mid--;  
19:      }  
20:      l2 = reverseList(l2);  
21:      while (l2) {  
22:        if (head->val != l2->val) return false;  
23:        head = head->next;  
24:        l2 = l2->next;  
25:      }  
26:      return true;  
27:    }  
28:    int countList(ListNode *head) {  
29:      int count = 0;  
30:      while(head) {  
31:        count++;  
32:        head = head->next;  
33:      }  
34:      return count;  
35:    }  
36:    ListNode *reverseList(ListNode *head) {  
37:      ListNode *pre = NULL;  
38:      while (head) {  
39:        ListNode *next = head->next;  
40:        head->next = pre;  
41:        pre = head;  
42:        head = next;  
43:      }  
44:      return pre;  
45:    }  
46:  };