题解 | #链表的回文结构#C语言详解（对一道会三道）

一、解题思想

 我的解题思想很朴素：

1. 首先找到中间结点
2. 将中间结点后半部分倒置
3. 分别从头结点和尾结点向中间遍历，检测在达到中间时刻之间val的值是否都相等

二、过程分解

为什么说对一道会三道呢？因为找到中间结点是一道题目，倒置又是一道题目，做完整道题目又是一道题目，所以我们可以将这道题目利用到极致。

①倒置

876. 链表的中间结点

⭐解题技巧：快慢指针法 + 哑结点（哨兵结点）

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* dummy = malloc(sizeof(struct ListNode)); 
    dummy->next = head;
    struct ListNode* fast = dummy;
    struct ListNode* slow = dummy;
    while(fast)
    {
        slow = slow->next;
        if(fast->next)
            fast = fast->next->next;
        else
            return slow;
    }
    return slow;
}

利用上述的方法我们可以找到中间结点：(在我下面的代码中若存在两个中间结点，则取前一个)

②反转链表

206. 反转链表

⭐解题技巧：记录前后结点

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* pre = NULL;
    struct ListNode* next = NULL;
    while(cur)
    {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

利用上面的方法我们完成转置：

三、完整代码

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));//哨兵结点
        dummy->next = A;
        ListNode*fast = dummy;
        ListNode*slow = dummy;
        while(fast && fast->next)  //获取中间结点
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        
        ListNode* cur = slow->next; //反转链表
        ListNode* next = cur->next;
        ListNode* pre = slow;
        slow->next = NULL; //防止形成环！！！！！
        while(1)
        {
            cur->next = pre;
            pre = cur;
            if(next == NULL) //注意判断的是next而不是cur->next
                break;
            cur = next;
            next = cur->next;
        }
        
        ListNode* head = A;
        ListNode* tail = cur;
        while(tail != slow)
        {
            if(head->val != tail->val)
                return false;
            tail = tail->next;
            head = head->next;
        }
        return true;
    }
};