面试题 02.06. 回文链表(C实现)

题目链接：面试题 02.06. 回文链表

先 找到回文链表的中间结点；
再 逆置中间节点往后的链表；
然后从回文链表的头开始遍历 和逆置后的链表一个一个比；
假如相等就迭代，知道遇到空；证明是回文链表
假如不相等那么就一定不是回文链表

//快慢指针找中间结点
struct ListNode* middleNode(struct ListNode* head)
{
    if(head == NULL || head->next ==NULL) return head;
    struct ListNode* slow = head;
    struct ListNode* fast = head;

    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

//头插法逆置
struct ListNode* reverser(struct ListNode* head)
{
    if(head == NULL || head->next == NULL) return head;
    struct ListNode* cur = head;
    struct ListNode* newHead = NULL;

    while(cur)
    {
        struct ListNode* curNext = cur->next;

        cur->next = newHead;
        newHead = cur;

        cur = curNext;
    }
    return newHead;
}


bool isPalindrome(struct ListNode* head){
    //先找到回文链表的中间节点
    struct ListNode* mid = middleNode(head);

    //找到中间结点后，逆置中间结点往后的链表
    struct ListNode* reverserNode = reverser(mid);
    
	//分别用 curFront 和 curMid 指向回文链表的头，和逆置链表的头
    struct ListNode* curFront = head;
    struct ListNode* curMid = reverserNode;

    while( curFront && curMid)
    {	//不相等就直接返回了，肯定不是回文链表
        if(curFront->val != curMid->val)
        {
             return false;           
        }
        else
        {//相等就迭代
            curFront = curFront->next;
            curMid = curMid->next;           
        }
    }
    return true;
}