The fastest two solutions space cost O(n) and O(1) in C with comments


  • 3
    //AC - 12ms;
    bool isPalindrome(struct ListNode* head)
    {
        int* arr = (int*)malloc(sizeof(int));
        int size = 0;
        struct ListNode* p = head;
        while(p) //collect all values;
        {
            size++;
            arr = (int*)realloc(arr, sizeof(int)*size);
            arr[size-1] = p->val;
            p = p->next;
        }
        for(int i = 0; i < size/2; i++) //symmetric;
            if(arr[i] != arr[size-i-1])
                return false;
        return true;
    }
    

    //AC - 12ms;
    bool isPalindrome(struct ListNode* head)
    {
        if(!head || !head->next) return true;
        struct ListNode *slow=head, *fast=head->next->next;
        while(fast && fast->next) //split into two halves while the right part might longer by 1 if the length of the link is odd;
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        if(fast == NULL) fast = slow->next;
        else fast = slow->next->next;
        slow->next = NULL;
        struct ListNode *cur, *pre, *next; //reverse the left linked and slow will become the head;
        cur = head->next;
        pre = head;
        pre->next = NULL;
        while(cur)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        // if(fast->val != slow->val) fast = fast->next; //if the first node is unequal, move fast forward to the next;
        while(fast)
        {
            if(fast->val != slow->val)
                return false;
            fast = fast->next;
            slow = slow->next;
        }
        return slow == NULL;
    }
    

  • 0
    W

    Fantastic code:

    while(fast && fast->next) {
      fast = fast->next->next;
      slow = slow->next;
    }
    

    But you maybe forget to delete pointer, how can we find the right part?
    : )


  • 0

    fast = slow->next; //now fast is pointing to the right part;

    slow->next = NULL; //terminate the left part;


  • 0
    W

    Yes. fast points to the right part. But you will never have a chance to delete the right part when you go out of function, isPalindrome.
    So we should append some codes:
    [Sorry, I don't know how to format subsequent code O_O]
    [Thanks. Now, I learn something OvO]

    while(fast) {
      ListNode* cur = fast;
      fast = fast->next;
      delete cur;
    }
    ... // some codes go here

  • 0

    Actually, I do not quite get your point here. But why do you want to delete the right part? There is no requirement in the problem.

    • We are required only to determine whether it is or not a palindromic string ^^

  • 0

    If you do not know how to format the code in OJ, you can check this which is the format used in Leetcode Discuss.


  • 0
    W

    Thank you. OvO


  • 0
    W

    Yes. I think these codes can produce right answer, but these codes aren't prefect. I maybe crap. ^^


  • 0

    You must be a perfectionist ##, anyway that's good enough now ^^


  • 0
    R

    if the input linked list is "MAAAM" then the o/p is wrong???


  • 0

    Sorry about the second one, it's not properly updated. Thanks for your pointing this out, thanks for sharing! The last false return statement is not right; I've updated now. Thanks again!


  • 1

    A issue of this code is that it can't check the ABBBA type because of if(fast->val != slow->val) fast = fast->next; If it's equal, the length between the two part is different. It won't return the correct result. What I do is count the length of the linked list. if (size%2) fast=fast->next. It will make sure the length is equal. Also, no need to check if(fast != slow) return false;


  • 0

    @Tanych You are quite true about this. Thank you for your sharing. I've updated it and also started an issue to fix it to adding more test cases. Thank you again.

    Still there is no need to count the length of the linked list actually.


  • 0

    @LHearen Thanks.


  • 0

    Using a more C++ way, still quite efficient.

    class Solution {
    public:
        bool isPalindrome(ListNode* head) 
        {
            vector<int> v;
            while(head)
            {
                v.push_back(head->val);
                head = head->next;
            }
            for(int i = 0; i < v.size()/2; ++i)
            {
                if(v[i] != v[v.size()-i-1]) return false;
            }
            return true;
        }
    };
    
    

  • 0

    Further simplified iterative solution in C++.

    class Solution {
    public:
        bool isPalindrome(ListNode* head) 
        {
            if(!head || !head->next) return true;
            ListNode *slow = head, *fast = head->next;
            while(fast && fast->next) //split into two halves while the first half can be one-node longer;
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            fast = slow->next;
            slow->next = NULL;
            ListNode newHead(0); //reverse the second half;
            ListNode *next = NULL, *p = fast;
            while(p)
            {
                next = p->next;
                p->next = newHead.next;
                newHead.next = p;
                p = next;
            }
            fast = newHead.next; //compare the two lists;
            while(fast)
            {
                if(fast->val != head->val) return false;
                fast = fast->next;
                head = head->next;
            }
            return fast == NULL;
        }
    };
    

Log in to reply
 

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