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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
bool isPail(struct ListNode* head ) {
    // write code here
    struct ListNode *start = head;
    struct ListNode *end = head;
    int cnt = 0, cnt1 = 0;
    if(head == NULL)
        return false;
    if(head->next == NULL)
        return true;
    while(end != NULL)
    {
        //printf("end->val=%d cnt=%d\n", end->val, cnt);
        cnt++;
        end = end->next;
   }
    printf("cnt=%d\n", cnt);
    end = head;
    while(cnt1 < cnt/2)
    {
        printf("end->val=%d cnt1=%d\n", end->val, cnt1);
        cnt1++;
        end = end->next;
    }
    printf("end->val=%d cnt1=%d\n", end->val, cnt1);
    if(cnt%2 != 0)
        end = end->next;
    printf("end->val=%d\n", end->val);
    struct ListNode* head2 = NULL;
    while(end != NULL)
    {
        struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
        p->val = end->val;
        p->next = head2;
        head2 = p;
        end = end->next;
    }
    while(start != NULL && head2 != NULL)
    {
        if(start->val != head2->val)
            return false;
        start = start->next;
        head2 = head2->next;
    }
    return true;
}