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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
#define    false    0
#define     true    1

int isPail(struct ListNode* head ) {
    
    // write code here
    struct ListNode* s = head;
    struct ListNode* p = head;
    struct ListNode* q = head;
    struct ListNode* slow = head;
    struct ListNode* save = head;
    struct ListNode* cur = head;
    int ListLength = 0;
    int q_count = 1;
    int p_count = 0;
    
    /*head == NULL*/
    if(head == NULL)
        return false;
    
    if(head ->next == NULL)
        return true;
    /*
    1. 将1/2 length之后的链表节点进行反转
    2. 进行回文判断
    */
    
    while(s != NULL){
        ListLength++;
        s = s->next;
    }
    
    while(q_count < ListLength/2){
        q_count++;
        slow = slow->next;
    }
    
    q = slow->next;
    cur = slow->next;
    /*反转q之后的链表节点*/
    while(q != NULL){
        save = q->next;
        q->next = cur;
        cur = q;    
        q = save;
    }
    
    /* cur 指向最有一个链表节点
    *使p 指向cur
    */
    q = cur;
    p = head;
    
    /*判断是否为回文链表*/
    for( ; p != q->next && q != p->next; p = p->next, q = q->next){
        if(p->val != q->val){
        return false;
        }
    }
    
return true;
}