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 }