链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

还是比较简单的，主要分为三个步骤，两种需掌握的函数实现

目录

主要思路过程，1，找到中间结点，2，反转中间结点往后的结点，3，遍历比较

以下是代码：

每日一表情包：

---

由于单链表没法让指针往回走，所以，我们要让它能往回走，以好比较，

主要思路过程，1，找到中间结点，2，反转中间结点往后的结点，3，遍历比较

我们用到，查找链表中间结点的操作，和反转链表的操作，

LeetCode：206反转链表-CSDN博客

LeetCode：876.链表的中间结点-CSDN博客

以下是代码：

博主C++还没学，对于这个题来说，C++比C语言只是多了最外面的那一圈，不影响！

（由于C++包含C语言，所以本篇其实还是用C实现的，因为这个题，没有C实现的选项）

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    //找到单链表的中间结点并返回
    struct ListNode* CheckMid(ListNode* A)
    {
        struct ListNode*  pslow = A , *pfast = A;
        while(pfast && pfast->next){
            pslow = pslow->next;
            pfast = pfast->next->next;
        }
        return pslow;
    }
    //逆转单链表/反转单链表，返回逆转后的头结点指针
    struct ListNode* ReverseListNode(ListNode* ps)
    {
        struct ListNode* ptail = NULL;
        while(ps){
            struct ListNode* pnext = ps->next;
            ps->next = ptail;
            ptail = ps;
            ps = pnext;
        }
        return ptail;
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        //assert(A);
        //先用快慢指针找到中间节点
        struct ListNode* pMid = CheckMid(A);
        //再逆转链表后半段，//此时后半段链表尾指向的是NULL，前半段指向的是后半段的尾
        struct ListNode* ptail = ReverseListNode(pMid);//逆转后的链表头结点
        //然后循环遍历判断
        while(ptail){
            if(ptail->val != A->val){
                return false;
            }
            ptail = ptail->next;
            A = A->next;
        }
        return true;
    }
};

每日一表情包：

阿巴阿巴，带那个赞再走吧！求求啦！