### 题目

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?

### 用一个Stack记录前半段的节点

• time: $O(n)$
• space: $O(n)$

#### 代码

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
if (head == null) { return true; }
boolean isOdd = ((size % 2) == 0)? false : true;
int mid = (size - 1) / 2;
for (int i = 0; i <= mid; i++) {
stack.offerFirst(cur.val);
cur = cur.next;
}
int rest = mid;
if (isOdd) { stack.pollFirst(); rest = mid-1; }
for (int i = 0; i <= rest; i++) {
Integer history = stack.pollFirst();
if (history == null || cur == null) { return false; }
if (history != cur.val) { return false; }
cur = cur.next;
}
if (!stack.isEmpty() || cur != null) { return false; }
return true;
}
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
}


### 反转前半段，再和后半段比较

    1->2->3->3->2->1


   head                    slow
|                       |
3->2->1     和          3->2->1

• time: $O(n)$
• space: $O(1)$

#### 代码

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
if (head == null || head.next == null) { return true; }
ListNode dummy = new ListNode(0);
while (fast != null && fast.next != null) {
fast = fast.next.next;
ListNode next = slow.next;
slow.next = dummy.next;
dummy.next = slow;
slow = next;
}
if (fast != null) { slow = slow.next; } // size is odd