Given a singly linked list, determine if it is a palindrome.Could you do it in O(n) time and O(1) space?
将链表值记录成数组，判断数组是否回文。时间复杂度O(n)，空间复杂度O(n)。
class Solution { public: bool isPalindrome(ListNode* head) { if (!head || !head->next) return true; vector<int> result; ListNode *cur = head; while (cur){ result.push_back(cur->val); cur = cur->next; } int i = 0, j = result.size() - 1; while (i<j){ if (result[i] != result[j]){ return false; } i++; j--; } return true; } }; 将链表后半段反转与前半段比较，给出两种写法。用双指针找链表中点，注意链表结点是奇数个还是偶数个。时间复杂度O(n)，空间复杂度O(1)。 class Solution { public: ListNode *reverseList(ListNode *head){ ListNode *pre = NULL, *temp; while(head){ temp = head->next; head->next = pre; pre = head; head = temp; } return pre; } bool isPalindrome(ListNode* head) { if(!head || !head->next) return true; ListNode *slow = head,*fast = head,*pre = NULL; while(fast && fast->next){ fast = fast->next->next; pre = slow; slow = slow->next; } pre->next = NULL; slow = reverseList(slow); while(head && slow){ if(head->val != slow->val) return false; head = head->next; slow = slow->next; } return true; } }; class Solution { public: ListNode *reverseList(ListNode *head){ ListNode *pre = NULL, *temp; while(head){ temp = head->next; head->next = pre; pre = head; head = temp; } return pre; } bool isPalindrome(ListNode* head) { if(!head || !head->next) return true; ListNode *slow = head,*fast = head; while(fast && fast->next){ fast = fast->next->next; slow = slow->next; } if(fast){//链表个数为奇数个 slow = reverseList(slow->next); } else{//链表个数为偶数个 slow = reverseList(slow); } while(slow){ if(head->val != slow->val) return false; head = head->next; slow = slow->next; } return true; } };GitHub-Leetcode: https://github.com/wenwu313/LeetCode