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：Two pointers
思路： Find mid + reverse + compare
Time Complexity: O(N) Space Complexity: O(N)
Solution Code：
class Solution {
public boolean isPalindrome(ListNode head) {
// find middle = slow
// 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
// slow fast
// 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
// slow fast
ListNode fast = head, slow = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) { // odd nodes
slow = slow.next;
}
// reverse
slow = reverse(slow);
// compare
fast = head;
while (slow != null) {
if (fast.val != slow.val) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
