[Algorithms] 7 - My Solution for Palindrome Linked List with O(N) Time Complexity & O(1) Space Complexity

Link for the problem

My understanding for the problem

• Idea: Reverse the nodes as slow pointer moves forward. Once the fast pointer reaches to the end of the list, then we compare the nodes from where the slow pointer is at and the nodes that are reversed.
• Edge cases:
  • What if the list has odd number of nodes? ex) [1,2,3,4,5]
  • The method that I used to figure out if the number of nodes is odd or even:
    • If fast pointer's next exists => even
    • If fast pointer's next does not exists => odd
  • When the list has only one node => true (2 does not matter)

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;
    }
};