Share my C++ solution, O(n) time and O(1) using 3 pointers


  • 0
    W
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if (head == NULL || head->next == NULL) return true;
            ListNode* front = new ListNode(0);
            ListNode* slow=head, *fast=head, *it=front, *tmp;
            
            while (fast && fast->next) {
                fast = fast->next->next;
                tmp = slow->next;
                slow->next = it->next;
                it->next = slow;
                slow = tmp;
            }
            
            if (fast) slow = slow->next;
            it = front->next;
            while (it && slow) {
                if (it->val != slow->val) return false;
                it = it->next;
                slow = slow->next;
            }
            
            return true;
        }
    };
    

Log in to reply
 

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