C++ Solution. O(1) space, O(n) time.


  • 1
    M

    This solution solves the problem in very few lines and I think it's very clear. Any comments are appreciated.

    class Solution {
    public:
        bool isPalindrome(ListNode *head) {
            int size = 0;
            ListNode *node = head, *mid, *tmp;
            while(node){
                size++; node = node->next;
            }
            node = NULL; mid = head;
            for(int i = 0; i < size/2; i++){
                tmp = mid->next;
                mid->next = node;
                node = mid;
                mid = tmp;
            }
            ListNode *right = mid, *left = node;
            if(size%2) right = right->next;
            while(left && right){
                if(left->val != right->val) return false;
                left = left->next;
                right = right->next;
            }
            return true;
        }
    };

Log in to reply
 

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