Accepted O(n) time O(1) space C++ code, but kinda weird, someone plz help me..

  • 0

    Below is my accepted C++ code, the basic idea is:

    1. Two pointers are used, one of them proceeds two steps a time and the other proceeds one step a time;
    2. Cut the list into two equal half, and reverse the first half;
    3. Compare the two half lists one by one.

    The code is accepted only if I put head->next = NULL; before returning the answer, otherwise I got a TLE. Can someone tell me why?

    class Solution {
        bool isPalindrome(ListNode* head) {
            if (!head || !head->next) return true;
            ListNode *p1 = head, *p2 = head;
            while (p2 && p2->next) {
                ListNode *temp = p1->next;
                if (p1 != head) {
                    p1->next = head;
                    head = p1;
                p1 = temp;
                p2 = p2->next->next;
            if (p2) p1 = p1->next;
            bool res = true;
            while (p1) {
                if (p1->val != head->val) 
                    res = false;
                p1 = p1->next;
                head = head->next;
            head->next = NULL; // Comment this out then a TLE occurs.
            return res;

  • 0

    I guess you formed a loop in the reversed list. To avoid a loop in the reversed list, it's better to let point to null at the beginning of the program. Of course we need another pointer to save the before

Log in to reply

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