C++: time O(n) and space O(1) by flipping the left half of the singly linked list


  • 0
    A
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            
            if(NULL == head)
            {
                return true;
            }
            
            ListNode* node = head;
            int len = 0;
            while(node)
            {
                ++len;
                node = node->next;
            }
            
            ListNode* leftHead = NULL;
            ListNode* rightHead = NULL;
            
            split(head, len, leftHead, rightHead);
            
            return isPalindrome(leftHead, rightHead, len);
            
        }
        
    private:
        void split(ListNode* inHead, int inLen, ListNode*& outLeftHead, ListNode*& outRightHead)
        {
            int midIndex = (inLen-1)/2;
            ListNode* node = inHead;
            for(int i=0;i<midIndex;++i)
            {
                node = node->next;
            }
            
            outLeftHead = node;
            outRightHead = node->next;
            
            // Flip the left half of the linked list
            ListNode* last = NULL;
            ListNode* curr = inHead;
            ListNode* next = inHead->next;
            for(int i=0;i<=midIndex;++i)
            {
                curr->next = last;
                last = curr;
                curr = next;
                next = next ? next->next:NULL;
            }
            
            outLeftHead = last;
            
        }
        
        bool isPalindrome(ListNode* leftHead, ListNode* rightHead, int len)
        {
            ListNode* leftNode = leftHead;
            ListNode* rightNode = rightHead;
            if((len & 0x1) == 1)
            {
                leftNode = leftNode->next;
            }
            
            while(leftNode)
            {
                if(leftNode->val != rightNode->val)
                {
                    return false;
                }
                leftNode = leftNode->next;
                rightNode = rightNode->next;
            }
            
            return true;
        }
        
        // get rid of the influence on the original linked list caused by split
        void restore()
        {}
    };

Log in to reply
 

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