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


  • 0
    Z

    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 {
    public:
        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
    A

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


Log in to reply
 

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