Description:
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?
Solution:
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head) return true;
auto slow = head;
auto fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// reverse right half of list
ListNode dummy(0);
while (slow) {
auto next = slow->next;
slow->next = dummy.next;
dummy.next = slow;
slow = next;
}
auto rev = dummy.next;
while (rev) {
if (rev->val != head->val) return false;
rev = rev->next;
head = head->next;
}
return true;
}
};
转载于:https://www.cnblogs.com/deofly/p/palindrome-linked-list.html
相关资源：JAVA上百实例源码以及开源项目
