思路：
遍历链表，统计链表的长度。反转链表前半部分遍历链表前半部分和后半部分的每个元素 时间复杂度为O(n)，空间复杂度为O(1) /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool isPalindrome(ListNode* head) { if(head==NULL||head->next==NULL) return true; int n=0; ListNode *p=head; while(p!=NULL){ p=p->next; ++n; } ListNode *q=head,*tag; for(int i=0;i<n/2;++i){ q=q->next; } tag=q; ListNode *r=head->next; p=head; while(p!=tag){ p->next=q; q=p; p=r; r=r->next; } p=q; if(n%2==1){ q=tag->next; }else{ q=tag; } while(p!=tag){ if(p->val!=q->val) return false; p=p->next; q=q->next; } return true; } };执行用时 : 24 ms, 在Palindrome Linked List的C++提交中击败了98.77% 的用户 内存消耗 : 12.5 MB, 在Palindrome Linked List的C++提交中击败了71.26% 的用户
