Palindrome Linked List
Leetcode #234 | Easy | Связный список | Два указателя | Быстрый и медленный | Стек
Идея
Вариант 1. Через стек
Вариант 2. За O(1) по памяти. Находим середину, разворачиваем вторую половину списка и сравниваем двумя указателями
Big-O
- Время
O(N) - Память
O(1)
Код
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
ListNode prev = slow, cur = slow.next;
while (cur != null) {
ListNode next = cur.next; cur.next = prev; prev = cur; cur = next;
}
ListNode middle = slow;
while (head != middle) {
if (head.val != prev.val) return false;
head = head.next; prev = prev.next;
}
return true;
}
}