链表的回文结构(C++超详细讲解)

矫情吗；* 2022-12-30 08:10 117阅读 0赞

### C++实现判断链表的回文结构 ###

*  思路
 *  代码实现

题目描述  
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

> 1->2->2->1

返回：true

# 思路 #

> 判断链表的回文结构，采取快慢指针的方法，即**快指针一次走两步，慢指针一次走一步**  
> 可将链表分为两种情况
> 
>  *  **链表含有偶数个节点**  
>     首先通过慢指针找到中间节点，如下图所示，当fast==NULL时停止  
>     ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]  
>     将中间指针后面的节点逆置  
>     ![在这里插入图片描述][20201224163413683.png]

> 最后两个指针一个从左向右一个从右向左，当pleft->next==pright时结束  
> ![在这里插入图片描述][20201224163549427.png]

>  *  链表含有奇数个节点的情况  
>     首先通过慢指针找到中间节点，当fast->next==NULL时结束  
>     ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]

然后逆置中间节点后的节点  
![在这里插入图片描述][20201224164057714.png]  
最后两个指针一个从左向右一个从右向左，当plef==pright时结束  
![在这里插入图片描述][20201224163956536.png]

# 代码实现 #

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };*/
    class PalindromeList {
        
    public:
        bool chkPalindrome(ListNode* A) {
        
            
        //1、链表为空或者只有一个节点则返回true
            if(A==NULL || A->next==NULL)
                return true;
        //2.链表多于一个节点
            ListNode * pfast = A;    //快指针
            ListNode * pslow = A;    //慢指针
            //偶数个节点时fast==NULL结束，奇数个节点时fast->next==NULL结束
            //while循环的条件是继续的条件，而我们思考的是while停止的条件，因此条件是反过来的
            while(!(pfast == NULL || pfast->next == NULL))    
            {
        
                pfast = pfast->next->next;    //快指针一次走两步
                pslow = pslow->next;           //慢指针一次走一步
            }
            
            //逆置节点,采用头插法,每次从链表中取出一个节点插入到pre节点之前
            ListNode * prev = pslow;    
            pslow = pslow->next;
            prev->next = NULL;    //中间节点置空
            while(pslow!=NULL)
            {
        
                ListNode * tmp =pslow->next;    //保存当前节点的后一个节点防止丢失
                pslow->next=prev;    //当前节点指向前一个节点
                prev=pslow;    //prev和pslow分别后移
                pslow=tmp;
            }
            
            
            ListNode * pleft = A;    //指向头节点
            ListNode * pright = prev;    //指向尾节点
            while(!(pleft==pright || pleft->next == pright))
            {
        
                if(pleft->val != pright->val)
                    return false;
                else
                {
        
                    pleft = pleft->next;
                    pright = pright->next;
                }
            }
            return true;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]: /images/20221120/925acb21ffd444f7875cdffb6e671a01.png
[20201224163413683.png]: /images/20221120/eb004756facf4f2898754e2e6a8058c3.png
[20201224163549427.png]: /images/20221120/bdd21da803cd4dc48d49dad47a821062.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]: /images/20221120/7cf1cdee650644a0b4652b309e318e8a.png
[20201224164057714.png]: /images/20221120/91663e6f837343f19981a5e93f2c595a.png
[20201224163956536.png]: /images/20221120/b01fd5be4f404748aebba198a4125da4.png