[C题目]力扣234. 回文链表

234. 回文链表 - 力扣（LeetCode）

 思路：

struct ListNode* MiddleNode(struct ListNode* head)
{
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    while(fast&&fast->next)//防止结点为奇数个时，fast->next先为NULL，fast应该写在fast->next的左边。
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
    //创建哨兵位的头结点
    struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
    newhead->next=NULL;//看作指向NULL结点
    struct ListNode* cur=head;
    while(cur)
    {
        struct ListNode* tmp=cur->next;
        cur->next=newhead->next;
        newhead->next=cur;
        cur=tmp;
    }
    return newhead->next;
}

bool isPalindrome(struct ListNode* head)
{
    struct ListNode* middle=MiddleNode(head);
    struct ListNode* newhead=reverseList(middle);
    struct ListNode* cur1=head;
    struct ListNode* cur2=newhead;
    while(cur2)//奇数个结点时，虽然后半段节点数比前半段结点数多一个，但当cur2指向middle时，cur1也存着middle的地址(指针域并没有被覆盖)，所以cur2->val依然等于cur1->val，不影响判断两个链表是否相等。
    {
        if(cur2->val!=cur1->val)
            return false;
        cur1=cur1->next;
        cur2=cur2->next;
    }
    return true;
}