# 234. Palindrome Linked List (Easy)

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

Example 1:

```Input: 1->2
Output: false```

Example 2:

```Input: 1->2->2->1
Output: true```

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

## Solutions

### 1.

``````class Solution {

// Recursive method.

ListNode headx = null;
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}

}

private boolean recurse(ListNode ptr) {
if (ptr == null) {
return true;
}

boolean rst = recurse(ptr.next);
if (!rst) {
return false;
}

if (headx.val != ptr.val) {
return false;
}

return true;
}
}
``````

### 2.

``````class Solution {

// Non-recursive method. Modify the list that move nodes on the right to head. Such that
// the elements of right part are in reverse order.

public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}

ListNode tmp = head;
// find out the length of the list
int len = 0;
while (tmp != null) {
tmp = tmp.next;
len++;
}

// reverse the front half of the list

int mid = len / 2;

// right points to the swapped node
// left is one step prior to right pointer
ListNode left = head;
ListNode right = left.next;
for (int i = 1; i < mid; i++) {
// move away the node pointed by right pointer
left.next = right.next;

// make the right node pointing to the head

// then make right pointer one step after left pointer
right = left.next;
}

// prepare 2 pointers of which one points the head and another points the middle
ListNode p1 = head;
ListNode p2 = head;

// p2Idx starts from 1
int p2Idx = mid + 1;
if (len % 2 == 1) {
p2Idx += 1;
}

// Move p2Idx-2 steps to reach desired position
for (int i = 0; i < p2Idx - 1; i++) {
p2 = p2.next;
}

// Move on the 2 pointers simultaneously and meanwhile compare the values. Once come
// across different values, representing the list is not palindrome.

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

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

return true;
}
}
``````