题解 | 判断一个链表是否为回文结构

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
            if(head==NULL||head->next==NULL){
                    return 1;//空和单节点提前判断
            }
        //拷贝链表
        ListNode*reverse_prehead=new ListNode(0);
        ListNode*rep=reverse_prehead;
        ListNode*p=head;
        while(p!=NULL){
            ListNode*newnode=new ListNode(p->val);
            rep->next=newnode;
            rep=newnode;
            p=p->next;
        }
         ListNode*reverse_head=reverse_prehead->next;
        //反转
        ListNode*pre=reverse_prehead;
        ListNode*cur=reverse_head;
        ListNode*after=reverse_head->next;
       
        while(cur!=NULL){
            cur->next=pre;
            pre=cur;
            cur=after;
            after=after->next;
        }
        delete reverse_prehead;
        reverse_head->next=NULL;
        ListNode*rehead=pre;
      //比较原链表和翻转链表
        ListNode*pb=rehead;
        for(ListNode*pa=head;pa!=NULL;pa=pa->next){
             if(pa->val!=pb->val){
                return 0;
             }
             else{
                   pb=pb->next;
             }
        }
           return 1;
        

      
       

    }
};