Share my easy understanding solution


  • 0
    R
    bool isPalindrome(ListNode* head) 
    {
        if (!head || !head->next)
            return true;
            
        ListNode *slow = head;
        ListNode *fast = head;
        ListNode *end1 = NULL;
        ListNode *start2 = NULL;
       
        while(fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
       
        if (slow == fast && slow->val != fast->next->val) // for case: 1->2
            return false;
           
        if (fast->next == NULL) // odd number of elements in linked list
        {
            end1 = slow;
            start2 = slow;
        }
        if (fast->next && fast->next->next == NULL) // even number of elements in linked list
        {
            end1 = slow; // end1 will be the head node for linkedlist 1
            start2 = slow->next; // start2 will be the head node for linkedlist 2
            if (end1->val != start2->val) // compare linked list1 and linked list 2 head node first
                return false;
        }
        
        // reverse linked list 1
        ListNode *prev = NULL;
        ListNode *ph = head;
        while (ph)
        {
            ListNode *temp = ph->next;
            ph->next = prev;
            prev = ph;
            ph = temp;
            if (ph == end1)
                break;
        }
        
        
        //compare
        ListNode *start1 = prev;
        start2 = start2->next;
        while (start1 && start2)
        {
            if (start1->val != start2->val)
                return false;
            start1 = start1->next;
            start2 = start2->next;
        }
        
        return true;
    }

Log in to reply
 

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