If you want O(n) time and O(1) space, this problem should not be an 'easy' one.


  • 17

    For an O(n)-O(1) answer, the common idea can be summarized as:

    1. find the middle.
    2. reverse half of the list (reverse the latter half would be more comprehensible).
    3. easily check for palindromic-ness as if it's a double-link list.
    4. restore the reversed half
    class Solution {
    

    public:
    inline void reverse(ListNode* head) {
    ListNode *node1, *node2, *node3;
    node1 = head;
    node2 = node1->next;
    node1->next = NULL;
    while(node2)
    {
    node3 = node2->next;
    node2->next = node1;
    node1 = node2;
    node2 = node3;
    }
    }

    bool isPalindrome(ListNode* head) {
        
        // lengths 0, 1 are palindrome
        if(!head || !head->next)
        {
            return true;
        }
        
        // length 2 goes simple judging
        if(!head->next->next)
        {
            return head->val == head->next->val;
        }
    
        // step 1: find middle and tail nodes
        ListNode *middle, *rbegin;
        middle = rbegin = head;
        while(rbegin->next)
        {
            if(rbegin->next->next)
            {
                middle = middle->next;
                rbegin = rbegin->next->next;
            }
            else
            {
                rbegin = rbegin->next;
            }
        }
        
        // step 2: reverse the latter half
        reverse(middle->next);
    
        // step 3: check for palindrome
        bool result = true;
        ListNode* node1 = head;
        ListNode* node2 = rbegin;
        while(node2)
        {
            if(node1->val != node2->val)
            {
                result = false;
                break;
            }
            
            node1 = node1->next;
            node2 = node2->next;
        }
        
        // step 4: restore the reversed latter half
        reverse(rbegin);
    
        return result;
    }
    

    };


  • 1
    class Solution {
    public:
        bool isPalindrome(ListNode *head) {
    		if (!head || !head->next)
    			return true;
    		ListNode *slow = head, *fast = head;
    		while (fast->next && fast->next->next) {
    			slow = slow->next;
    			fast = fast->next->next;
    		}
    		fast = slow->next;
    		slow->next = NULL;
    		ListNode *second = reverseList(fast);
    		while (second && second->val == head->val) {
    			second = second->next;
    			head = head->next;
    		}
    		slow->next = fast;
            return second == NULL;
        }
    private:
        ListNode *reverseList(ListNode *head) {
    		ListNode *pre = NULL, *next = NULL;
    		while (head) {
    			next = head->next;
    			head->next = pre;
    			pre = head;
    			head = next;
    		}
    		return pre;
    	}
    };

  • -1
    Q

    I reversed the first half except head, which is very convenient in my opinion. below is my code. len/2-2 node(s) been modified and restored.

    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if(!head || !head->next) return 1;
            int len=1;
            ListNode *r=head;
            for(;r->next;r=r->next) { ++len; }
            if(head->val!=r->val) return 0; // early terminated if head->val!=tail->val
            // reverse the first half except head, only if len>=6
            int i=len/2-2;
            ListNode *ml,*mr, *p,*q;
            p=head->next, q=p->next;
            for(;i>0;--i) {
                r=q->next;
                q->next=p;
                p=q;
                q=r;
            }
            // record the boundaries in the middle
            ml=p;
            mr=q;
            // adjust the start pos of second half
            if(len&1) q=q->next;
            // palindrome check
            i=len/2-1;
            int isok=1;
            for(;i>0;--i) {
                if(p->val!=q->val) { isok=0; break; }
                p=p->next, q=q->next;
            }
            // restore the reversed half
            i=len/2-2;
            p=ml, q=mr;
            for(;i>0;--i) {
                r=p->next;
                p->next=q;
                q=p;
                p=r;
                
            }
            return isok;
        }
    };

  • 1
    C

    You could remove the unused comments in your code, so it seems more readability.


  • 0
    Y
    /**
     * 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 == nullptr || head->next == nullptr)
                return true;
            ListNode *slow = head, *fast = head;
            while(fast->next && fast->next->next) {
                slow = slow->next;
                fast = fast->next->next;
            }
            slow->next = reverse_list(slow);
            slow = slow->next;
            while(slow) {
                if(head->val != slow->val)
                    return false;
    
                slow = slow->next;
                head = head->next;
            }
            return true;
        }
    private:
        ListNode *reverse_list(ListNode *slow) {
            ListNode *prev = slow;
            ListNode *cur, *tmp_next = prev->next;
            while(tmp_next) {
                cur = tmp_next;
                tmp_next = cur->next;
                cur->next = prev;
                prev = cur;
            }
            slow->next->next = nullptr;
            return cur;
        }
    };
    

Log in to reply
 

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