28ms C++ Solution with logic demonstration (Not the best but might help some people to understand)


  • 0
    A
    class Solution 
    {
    public:
        bool isPalindrome(ListNode* head) 
        {
            ListNode* count = head, *left_head = head;
            ListNode* left_end, *right_head;
            int size = 0, counter = 0;
            //get the size of the Linked list 
            while(count != NULL){
                size+=1; count = count->next;
            }
            //if size is 1, it is Palindrome
            if (size == 1)
                return true;
            
            //get the location for left_end pointer so that we can apply to the algorithm below
            int locationForLeftEnd = size/2-1;
            
            /*Logic Demonstration
            =========================================================================
            Step.1  Set up all pointers such as left_head, left_end, right_head
            =========================================================================
            left_head    left_end                 right_head                    head
              [ 1 ] -----> [ 2 ] -----> [ 3 ] -----> [ 2 ] -----> [ 1 ] -----> [NULL]
            =========================================================================*/
            while(head!=NULL)
            {
                if(counter==locationForLeftEnd)
                    left_end = head;
            
                // depends on the size of the Linked list (odd/even), the location is different
                if(counter == locationForRightHead(size))  
                    right_head = head;
                    
                counter+=1;
                head=head->next;
            }
            
            /*Logic Demonstration
            =========================================================================
            Step.2  Set left_end->next to NULL
            =========================================================================
            left_head    left_end                 right_head                    head
              [ 1 ] -----> [ 2 ] -----> [NULL]       [ 2 ] -----> [ 1 ] -----> [NULL]
            =========================================================================*/
            left_end->next = NULL;
            
            /*Logic Demonstration
            =========================================================================
            Step.3  Reverse the left side Linked list
            =========================================================================
            left_head                             right_head                    
              [ 2 ] -----> [ 1 ] -----> [NULL]       [ 2 ] -----> [ 1 ] -----> [NULL]
            =========================================================================*/
            left_head = reverse_linkedList(left_head);
            
            /*Logic Demonstration
            =========================================================================
            Step.4  Compare two Linked lists and return true/false if they are the same
            =========================================================================
            left_head                             right_head                    
              [ 2 ] -----> [ 1 ] -----> [NULL]       [ 2 ] -----> [ 1 ] -----> [NULL]
            =========================================================================*/
            return compare_twoLinkedlists(left_head, right_head);
        }
        
        bool compare_twoLinkedlists(ListNode* left, ListNode* right)
        {
            while(left != NULL && right != NULL)
            {
                if(left->val != right->val)
                    return false;
                left = left->next;
                right = right->next;
            }
            return true;
        }
        
        ListNode* reverse_linkedList(ListNode* node)
        {
            ListNode* prev = NULL;
            while(node!=NULL)
            {
                ListNode* temp = node->next;
                node->next = prev;
                prev = node;
                node = temp;
            }
            return prev;
        }
        
        int locationForRightHead(int size)
        {
            if (size%2==0)
                return size/2;
            else
                return size/2+1;
        }
    };

Log in to reply
 

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