力ボタン234.エコーチェーン

チェーンテーブルが返信チェーンテーブルであるかどうかを判断してください.
例1:
入力:1->2出力:false例2:
入力:1->2->2->1出力:trueステップ:O(n)時間複雑度とO(1)空間複雑度でこの問題を解決できますか?
考え方:中間ノードを探して、後半のチェーンテーブルを逆置きし、後半のチェーンテーブルの長さは元のチェーンテーブル以下であるため、後半のチェーンテーブルに基づいて比較サイクル回数を決定する

#include
#include
using namespace std;

typedef struct ListNode
{
    int val;
    ListNode *next;
} ListNode,*PtrToNode;

void Print(PtrToNode N)
{
    PtrToNode p = N;
    while(p!=NULL)
    {
        printf("%d ",p->val);
        p = p->next;
    }
    printf("
");
    return;
}

PtrToNode Insert(PtrToNode N,int e)
{
    PtrToNode p = (PtrToNode)malloc(sizeof(ListNode));
    p->val = e;
    p->next = NULL;
    if(N == NULL)
    {
        N = p;
    }
    else
    {
        PtrToNode q = N;
        while(q->next != NULL)
        {
            q = q->next;
        }
        q->next = p;
    }
    return N;
}

class Solution
{
public:
    bool isPalindrome(ListNode* head)
    {
        int n = 0;
        ListNode *p = head;
        while(p!=NULL)
        {
            n++;
            p = p->next;
        }
        p = head;
        n = n/2;
        while(n>0)
        {
            p = p->next;
            n--;
        }

        ListNode *q;
        ListNode *temp = NULL;
        while(p!=NULL)
        {
            q = p->next;
            p->next = temp;
            temp = p;
            p = q;
        }

        while(temp!=NULL)
        {
            if(temp->val != head->val)
            {
                return false;
            }
            temp = temp->next;
            head = head->next;
        }
        return true;
    }
};

int main()
{
    Solution s;
    PtrToNode N,M;
    N = NULL;
    N = Insert(N,1);
    N = Insert(N,2);
//    N = Insert(N,3);
    N = Insert(N,3);
    N = Insert(N,2);
    N = Insert(N,1);


    Print(N);
    if(s.isPalindrome(N))
    {
        printf("RIGHT
");
    }
    else
    {
        printf("WRONG
");
    }
//
//    Print(M);


    return 0;
}