C++ solution using reverseList


  • 0
    F
    /**
     * 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) {
            ListNode* fast = head;
            ListNode* slow = head;
            
            while(fast != nullptr && fast->next != nullptr){
                slow = slow->next;
                fast = fast->next->next;
            }
            
            if(fast != nullptr) slow = slow->next;
            
            slow = reverseList(slow);
            
            fast = head;
            while(slow != nullptr){
                if(fast->val != slow->val) return false;
                fast = fast->next;
                slow = slow->next;
            }
            
            return true;
        }
        
        ListNode* reverseList(ListNode* head){
            if(head == nullptr || head->next == nullptr) return head;
            
            ListNode* node = reverseList(head->next);
            head->next->next = head;
            head->next = nullptr;
            
            return node;
        }
    };

Log in to reply
 

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