# Palindrome List

Given a singly linked list, determine if its a palindrome. Return 1 or 0 denoting if its a palindrome or not, respectively.

Notes:

• Expected solution is linear in time and constant in space.
For example,

```List 1-->2-->1 is a palindrome.
List 1-->2-->3 is not a palindrome.```
Method:

Reverse the second half of the linked list, and then scan the linkedlist from the start and end at the same time.

For example, 1-> 2 -> 1 becomes 1 -> 2 and 2 <- 1
1 -> 2 -> 2 -> 1 becomes 1-> 2 and 2 <- 1

Solution:

Time: o(n)
Space: O(1)

/**
* Definition for singly-linked list.
* class ListNode {
*     public int val;
*     public ListNode next;
*     ListNode(int x) { val = x; next = null; }
* }
*/
public class Solution {
// null <- 1 <- 2 -> 3 -> 4
private ListNode reverse(ListNode A) {
if (A == null || A.next == null) return A;
ListNode curr = A;
ListNode prev = null;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}

private ListNode mid(ListNode A) {
ListNode slow = A;
ListNode fast = A.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// if list is even, return the next slow as mid
// for example, 1 -> 2 -> 3 -> 4, we want 3
if (fast != null) {
slow = slow.next;
}
return slow;
}

public int lPalin(ListNode A) {
ListNode mid = mid(A);
ListNode tail = reverse(mid);
while (A != null && tail != null) {
if (A.val != tail.val) {
return 0;
}
A = A.next;
tail = tail.next;
}
return 1;
}
}