/**
Given the head of a singly linked list, return true if it is a palindrome or
false otherwise.
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
Constraints:
The number of nodes in the list is in the range [1, 10⁵].
0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space? Related Topics栈 | 递归 | 链
表 | 双指针
👍 1514, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
int len = 0;
ListNode tmp = head;
while(tmp != null) {
len++;
tmp = tmp.next;
}
int[] halfArr = new int[len / 2];
int index = 0;
tmp = head;
while (index < len / 2) {
halfArr[index] = tmp.val;
index++;
tmp = tmp.next;
}
if (len % 2 == 1) {
index++;
tmp = tmp.next;
}
index = 0;
while (index < len / 2) {
if (halfArr[len / 2 - 1 - index] != tmp.val) {
return false;
}
tmp = tmp.next;
index++;
}
return true;
}
}
//leetcode submit region end(Prohibit modification and deletion)
