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 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /** * 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; //use slow and fast pointer to find the mid node ListNode* slow = head, * fast = head; while(fast && fast->next && fast->next->next){ slow = slow->next; fast = fast->next->next; } //reverse the right half list ListNode* l1 = head; ListNode* l2 = slow->next; slow->next = NULL; l2 = reverse(l2); //compare the two lists‘s node vale while(l2){ if(l1->val != l2->val) return false; l1 = l1->next; l2 = l2->next; } return true; } ListNode* reverse(ListNode* head){ ListNode* pre = NULL; ListNode* cur = head; while(cur){ ListNode* tmp = cur->next; cur->next = pre; pre = cur; cur = tmp; } return pre; }}; |
原文：http://www.cnblogs.com/zhxshseu/p/e8090dec49496a49d26a24e2da773bce.html