234. Palindrome Linked List

main idea is not difficult:

1. divide the list into two halves A and B
1. reverse B
1. check if A == B

however, too many implementation details:

how to divide the list into 2 halves?

quick answer is using fast and slow pointers, problem is using while (fast->next && fast->next->next) or while (fast && fast->next). we should handle both even elements and odd elements. Here both fast and slow start from 1st element, supposing there are 2n+1 (which is 1 + 2n) / 2n+2 (which is 1 + 2n+1) elements in total.

In case while (fast->next && fast->next->next), fast would stop at the last element instead of nullptr. Consequently, slow would stops at 1 + n. Hence, slow->next would be the head of second half head2 no matter there are 2n+1/2n+2 elements.

why if (! head)

precondition of while (fast->next && fast->next->next) is fast != nullptr

slow->next = reverseList(slow->next) to link the reversed second half to first half

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (! head) {
            return true;
        }
        
        ListNode* fast = head;
        ListNode* slow = head;
        //suppose there are 2n+1/2n+2 elements in total
        //fast and slow start from 1st element
        //fast stops at 2n+1/2n+2
        //slow stops at n+1
        //in either case slow->next is head of second half
        while (fast->next && fast->next->next) { //vs while (fast && fast->next), fast stops at last element instead of nullptr
            slow = slow->next;
            fast = fast->next->next;
        }
        
        slow->next = reverseList(slow->next);
        ListNode* head2 = slow->next; 
        
        while (head2) {
            if (head->val != head2->val) {
                slow->next = reverseList(slow->next);
                return false;
            }
            head = head->next;
            head2 = head2->next;
        }
        slow->next = reverseList(slow->next);
        return true;
    }
private:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* nxt = head;
        while (nxt) {
            ListNode* cur = nxt;
            nxt = nxt->next;
            cur->next = pre;
            pre = cur;
        }
        return pre;
    }
};

234. Palindrome Linked List - cocoder39/coco39_LC GitHub Wiki