My 17ms C++ solution, easy to understand, with comments


  • 0
    Z

    Basic idea is to find the middle point of the linked list, then reverse the 2nd half.
    Notice that since reversed linked list is just half as long as the original one, one just need to compare half of the original linked list with the reversed one.

    class Solution {
    private:
        ListNode* reverseLinkedList(ListNode* head) {
            // Special case
            if ( (!head) || !(head->next) ) {
                return head;
            }
            // Normal case
            else {
                ListNode* prev = nullptr;
                ListNode* curr = head;
                while (curr != nullptr) {
                    ListNode* nex = curr->next;
                    curr->next = prev;
                    prev = curr;
                    curr = nex;
                }
                return prev;
            }
        }
        
        // head1 is twice as long as head2
        bool equivalentLinkedList(ListNode* head1, ListNode* stopNode, ListNode* head2) {
            // Special cases
            if (!head1) {
                if (!head2) {
                    return true;
                }
                else {
                    return false;
                }
            }
            else if (!head2) {
                return false;
            }
            // Normal case
            else {
                while ( (head1 != stopNode) && (head1->val == head2->val) ) {
                    head1 = head1->next;
                    head2 = head2->next;
                }
                if ( (head1 != stopNode) || (head2 != nullptr) ) {
                    return false;
                }
                else {
                    return true;
                }
            }
        }
        
    public:
        bool isPalindrome(ListNode* head) {
            // Special case
            if ( (!head) || !(head->next) ) {
                return true;
            }
            else if (!(head->next->next)) {
                return (head->val == head->next->val);
            }
            // Normal case
            else {
                // Step 1: determine the center of linked-list
                // define 2 pointers with different moving speed
                // In case of 1->2->3->2->1, slow points to 3, fast points to 1
                // In case of 1->2->3->3->2->1, slow points to 2nd 3, fast points to NULL
                ListNode* slow = head;
                ListNode* fast = head;
                while ( (fast != nullptr) && (fast->next != nullptr) ) {
                    slow = slow->next;
                    fast = fast->next->next;
                }
                
                // Step 2: reverse the 2nd half of the linked-list
                // Case 2.1: 1->2->3->2->1, slow (pointing to 3)'s next is reversed
                if ( (fast != nullptr) && (fast->next == nullptr) ) {
                    ListNode* reversed = reverseLinkedList(slow->next); // 1->2->NULL
                    // now compare each node
                    return equivalentLinkedList(head, slow, reversed);
                }
                // Case 2.2: 1->2->3->3->2->1, slow (pointing to 2nd 3) is reversed
                else {
                    ListNode* reversed = reverseLinkedList(slow);  // 1->2->3->NULL
                    // now compare each node
                    return equivalentLinkedList(head, slow, reversed);
                }
            }
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.