解法一:递归
如果不考虑递归的栈开销的话,满足空间复杂度的要求。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
ListNode cur;
public boolean isPalindrome(ListNode head) {
cur = head;
return dfs(head);
}
private boolean dfs(ListNode p) {
if (p == null) {
return true;
}
boolean ans = dfs(p.next) && (p.val == cur.val);
cur = cur.next;
return ans;
}
}