Simple C++ Solution Reverting Half List, O(N) Time, O(1) Space


  • 0
    M
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if (!head) return true;
            
            int len = 0;
            ListNode *tmp = head;
            while (tmp) { ++len; tmp = tmp->next; }
            
            ListNode *cur = head, *prev = 0, *ll = 0, *lr = 0;
            for (int i = 0; i < len / 2; ++i) {
                tmp = cur->next;
                cur->next = prev;
                prev = cur;
                cur = tmp;
            }
            
            ll = prev;
            lr = len % 2 == 0 ? cur : cur->next;
            for (int i = 0; i < len / 2; ++i) {
                if (ll->val != lr->val) return false;
                ll = ll->next;
                lr = lr->next;
            }
            return true;
        }
    };
    

Log in to reply
 

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