Ссылка на проблему

Мое понимание проблемы

Идея: Переворачивать узлы по мере продвижения медленного указателя вперед. Как только быстрый указатель достигает конца списка, мы сравниваем узлы, в которых находится медленный указатель, и узлы, которые были перевернуты.
Краевые случаи:
- Что делать, если в списке нечетное количество узлов? Например, [1,2,3,4,5].
- Метод, который я использовал, чтобы выяснить, является ли количество узлов нечетным или четным:
  - Если следующий указатель существует => четный
  - Если следующий указатель не существует => odd
- Если в списке только один узел => true (2 не имеет значения)


class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* dummy = new ListNode();
        ListNode* slowPrev = dummy, *slow = head, *slowNext = slow, *fast = head;
        dummy->next = head;
        bool isOdd = false;

        while(fast){

            // Move fast forward
            if(fast->next){
                fast = fast->next->next;
            }else{
                fast = fast->next;
                isOdd = true;
            }

            // Reverse slow
            slowNext = slow->next;
            slow->next = slowPrev;
            slowPrev = slow;
            slow = slowNext;
        }

        // Detach dummy node (otherwise will get memory access error)
        head->next = nullptr;
        delete dummy;

        if(isOdd){
            slowPrev = slowPrev->next;
        }

        while(slowPrev && slow){
            if (slow->val != slowPrev->val) return false;
            slowPrev = slowPrev->next;
            slow = slow->next;
        }

        return true;
    }
};

Вход в полноэкранный режим Выход из полноэкранного режима

[Алгоритмы] 7 — Мое решение для палиндромного связного списка с O(N) временной сложностью и O(1) пространственной сложностью

Мое понимание проблемы