C++, reverse halve of list, then campare


  • 1
    M

    /**

    • Definition for singly-linked list.
    • struct ListNode {
    • int val;
      
    • ListNode *next;
      
    • ListNode(int x) : val(x), next(NULL) {}
      
    • };
      */

    class Solution {

    public:

    bool isPalindrome(ListNode* head) {

        if (!head || !head->next)
            return true;
        
        ListNode * slow, *fast;
        slow = fast = head;
        
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        if (fast) {  
           // odd number 
           slow->next = reverseList(slow->next);  
           slow = slow->next;  
        }else{  
           // even number  
           slow = reverseList(slow);  
        }
        
        while (slow) {  
            if (head->val != slow->val) {  
                return false;  
            }  
            slow = slow->next;  
            head = head->next;  
        }  
        return true;
    }
    
    ListNode* reverseList(ListNode* head) {
        ListNode* pReversedHead = NULL;
        ListNode* pNode = head;
        ListNode* pPrev = NULL;
        
        while(pNode != NULL) {
            ListNode* pNext = pNode->next;
            if(pNext == NULL)
                pReversedHead = pNode;
            
            pNode->next = pPrev;
            pPrev = pNode;
            pNode = pNext;
        }
        
        return pReversedHead;
    }
    

    };


Log in to reply
 

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