234. Palindrome Linked List，palindromelinked

234. Palindrome Linked List，palindromelinked

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?

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 bool isPalindrome(struct ListNode* head) {
 9     struct ListNode* q;                      //P走一步，q走兩部，q到尾部，p到中間節點
10     struct ListNode* p;
11     struct ListNode* head2;
12     p = head;
13     q = head;
14     if(head == NULL)                            //空鏈表也算
15         return 1;
16     while(q->next != NULL)
17     {
18         p = p->next;
19         q = q->next;
20         if(q->next == NULL)
21             break;
22         q = q->next;
23     }
24     head2 = p;
25     while(p != q)                                //後部分鏈表逆置
26     {
27         head2 = head2->next;
28         p->next = q->next;
29         q->next = p;
30         p = head2;
31     }
32     p = head;                                   //從開頭遍歷2個鏈表
33     q = head2;
34     while(p != NULL && q != NULL)
35     {
36         if(p->val != q->val)
37             break;
38         p = p->next;
39         q = q->next;
40             
41     }
42     if( NULL == p || NULL == q)               //達到尾結點，即是回文鏈表
43         return 1;
44     return 0;
45 }