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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */

 typedef struct ListNode* LinkList;

//统计链表元素节点个数
int NumCount(LinkList L);
//翻转链表
LinkList reverseList(LinkList head);
LinkList reverse(LinkList pre,LinkList cru);

bool isPail(struct ListNode* head ) {
    // write code here
    bool flag;
    if(head==NULL||head->next==NULL)
        return flag=true;
    
    int num=NumCount(head);

    int i;
    LinkList h,s;
    s=head;
  	//找到中值节点，并分离成两个链表
    for(i=1;i<(num/2);i++)
        s=s->next;
    
    h=s->next;
    s->next=NULL;
	//将后半部分链表翻转，进行判断
    h=reverseList(h);
    LinkList s1,s2;
    s1=head;
    s2=h;
    while(s1&&s2){
        if(s1->val!=s2->val)
            return flag=false;

        s1=s1->next;
        s2=s2->next;    
        
    }
    return flag=true;
    
}
int NumCount(LinkList L){
    LinkList s;
    s=L;
    int cot=0;
    while(s){
        s=s->next;
        cot++;
    }
    return cot;
}

LinkList reverseList(LinkList head){
    if(head==NULL||head->next==NULL)
        return head;

    head=reverse(NULL,head);
    return head;
}

LinkList reverse(LinkList pre,LinkList cru){
    if(cru==NULL)
        return pre;
    
    LinkList temp;
    temp=cru->next;
    cru->next=pre;
    return reverse(cru,temp);
}