LeetCode 234. 判断链表是否回文
原题链接
简单
作者:
YYC
,
2020-07-11 09:46:35
,
所有人可见
,
阅读 432
栈
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
ArrayDeque<Integer> stack = new ArrayDeque<>();
while (fast != null && fast.next != null){
stack.push(slow.val);
fast = fast.next.next;
slow = slow.next;
}
if (fast != null){
slow = slow.next;
}
while (slow != null){
if (slow.val != stack.pop()){
return false;
}
slow = slow.next;
}
return true;
}
}
反转
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
if (fast != null){
slow = slow.next;
}
slow = reverse(slow);
fast = head;
while (slow != null){
if (slow.val != fast.val){
return false;
}
slow = slow.next;
fast = fast.next;
}
return true;
}
private ListNode reverse(ListNode head){
ListNode ans = null;
while (head != null){
ListNode next = head.next;
head.next = ans;
ans = head;
head = next;
}
return ans;
}
}