Palindrome Linked List
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, 105].
0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
思路一:刚开始想用栈来实现,后面想想直接用双端队列,先把链表转换成双端队列,然后取队列两头进行对比
public static boolean isPalindrome(ListNode head) {
Deque<Integer> deque = new ArrayDeque<>();
while (head != null) {
deque.push(head.val);
head = head.next;
}
while (deque.size() > 1) {
if (!deque.pollFirst().equals(deque.pollLast())) {
return false;
}
}
return true;
}
思路二:看了一下题解,有更好的算法,用快慢指针,反转链表的后半部分,最后直接从中间开始比较链表的值
标签:deque,head,false,链表,easy,234,return,true,leetcode From: https://www.cnblogs.com/iyiluo/p/17038671.html