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?
/**
* 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) {
auto m = mid(head);
auto l = head, r = reverse(m);
// r在reverse时next和前面的已经断了,因此用r作判断。
while (r != NULL) {
if (l->val != r->val) return false;
l = l->next;
r = r->next;
}
return true;
}
private:
ListNode* mid(ListNode *head) {
auto slow = head, fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
if (fast != NULL) slow = slow->next; // odd nodes: let right half smaller
return slow;
}
ListNode* reverse(ListNode *head) {
ListNode *node = head, *prior = NULL;
while (node != NULL) {
auto next = node->next;
node->next = prior;
prior = node;
node = next;
}
return prior;
}
};
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode first = head, sec = head;
while (sec != null && sec.next != null) {
first = first.next;
sec = sec.next.next;
}
if (sec != null) {
first = first.next; // odd nodes: let right half smaller
}
ListNode pre = null;
while (first != null) {
ListNode next = first.next;
first.next = pre;
pre = first;
first = next;
}
sec = pre;
first = head;
while (sec != null) {
if (first.val != sec.val) {
return false;
}
first = first.next;
sec = sec.next;
}
return true;
}
}