# Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Could you do it in O(n) time and O(1) space?

## Solution

1. We can create a new list in reversed order and then compare each node. The time and space are O(n).
2. We can use a fast and slow pointer to get the center of the list, then reverse the second list and compare two sublists. The time is O(n) and space is O(1).

## Code

``````/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isPalindrome(ListNode head) {
return true;

ListNode p = head;
ListNode prev = new ListNode(head.val);

while(p.next != null){
ListNode temp = new ListNode(p.next.val);
temp.next = prev;
prev = temp;
p = p.next;
}

ListNode p1 = head;
ListNode p2 = prev;

while(p1!=null){
if(p1.val != p2.val)
return false;

p1 = p1.next;
p2 = p2.next;
}

return true;
}

public boolean isPalindrome_2(ListNode head) {
return true;

//find list center
ListNode fast = head;
ListNode slow = head;

while(fast.next!=null && fast.next.next!=null){
fast = fast.next.next;
slow = slow.next;
}

ListNode secondHead = slow.next;
slow.next = null;

//reverse second part of the list
ListNode p1 = secondHead;
ListNode p2 = p1.next;

while(p1!=null && p2!=null){
ListNode temp = p2.next;
p2.next = p1;
p1 = p2;
p2 = temp;
}

//compare two sublists now
ListNode p = (p2==null?p1:p2);
ListNode q = head;
while(p!=null){
if(p.val != q.val)
return false;

p = p.next;
q = q.next;

}

return true;
}
}
``````