Share my C++ solution.


  • 0
    A
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if(!head || !head->next)
                return true;
            ListNode *p = head, *q = head->next;//p,q is not NULL
            while(q && q->next)
            {
                p = p->next;
                q = q->next->next;
            }
            ListNode *mid = p->next;
            ListNode *r = p;
            p->next = NULL;
            reverse(mid);
            p = head;
            q = mid;
            bool ret = true;
            while(q)
            {
                if(q->val != p->val)
                {
                    ret = false;
                    break;
                }
                q = q->next;
                p = p->next;
            }
            reverse(mid);
            r->next = mid;
            return ret;
        }
        
         void reverse(ListNode *&head)
         {
             ListNode *fakeNode = new ListNode(0);//next is NULL
             ListNode *p = head;
             while(p)
             {
                 ListNode *q = p->next;
                 p->next = fakeNode->next;
                 fakeNode->next = p;
                 p = q;
             }
             head = fakeNode->next;
             delete fakeNode;
         }
    };

Log in to reply
 

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