## 题目描述

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?

## 代码

### Approach #1 Copy into ArrayList and then Use Two Pointer Technique

Complexity Analysis
• Time complexity : O(n)
• Space complexity : O(n)
/**
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> vals = new ArrayList<>();
while (currentNode != null) {
currentNode = currentNode.next;
}
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}

### Approach #2 Recursive - DFS

class Solution {
private ListNode frontPointer;
}
private boolean recursivelyCheck(ListNode currentNode) {
if (currentNode != null) {
if (!recursivelyCheck(currentNode.next)) return false;
if (currentNode.val != frontPointer.val) return false;
frontPointer = frontPointer.next;
}
return true;
}
}

### Approach #3 Reverse Second Half In-place

class Solution {
if (head == null) return true;
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) result = false;
p1 = p1.next;
p2 = p2.next;
}
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
ListNode prev = null;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}