题解 | #链表的回文结构#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/


/*
思路：将链表的节点逆置，然后得到的新链表与原链表进行比较，看是否相等，相等的话那么这个链表就具有回文结构
*/

/*
思路一：创建新的数组，遍历原链表，将链表节点中的值放入数组中，在数组中判断是否为回文结构

*/


// class PalindromeList {
// public:
//     bool chkPalindrome(ListNode* A) {
//         int arr[900]={0};
//         ListNode *pcur=A;
//         int i=0;
//         while(pcur)//遍历原链表，pcur不能为空
//         {
//             //将链表中每个节点的值放到arr中
//             arr[i]=pcur->val;
//             i++;
//             pcur=pcur->next;//换下一个节点
//         }
//         //i即节点的个数，因为我们的i一直在进行++操作

//         //找中间节点，判断是否为回文数字
//         int left=0;
//         int right=i-1;//i是数组中数据的有效个数
//         //我们比较left和right的下标的数字的大小，相等的话我们就让两个指针一直走，直到遍历整个数组
//         while(left<right)
//         {
//             if(arr[left]!=arr[right])
//             {
//                 //那么肯定不是回文结构
//                 return false;
//             }
//             right--;
//             left++;

//         }
//         //说明是回文结构，因为已经跳出循环了
//         return true;
//     }
// };


//这道题我们注意：我们开辟了空间，arr[900]
//但是假如我们碰到的题没有对链表节点个数进行限制的话，那么这种思路的话肯定是不行的

//除此之外，该思路只能在牛客上通过，力扣是不行的




//思路二：反转链表
/*
1.找链表的中间节点（快慢指针） 
2.将中间节点及中间节点之后的链表进行反转
此时我们的right和left就能接着后面进行比较了
*/
/*反转链表的思路：
创建三个指针，n1 n2 n3
解释下思路二：
 一开始我们的n1是空指针，n2指向的是1，n3指向的是2
 我们将n2的指向改变指向n1，然后1就指向了空指针1->NULL

 然后我们将n1放到n2的位置,n2放到n3的位置，那么现在n1指向的是1,n2指向的是2，n3指向的是3
 我们将n2的指向改变指向为n1   2->1->NULL

 然后我们将n1放到n2的位置,n2放到n3的位置，那么现在n1指向的是2,n2指向的是3，n3指向的是4 我们将n2的指向改变指向为n1     3->2->1->NULL

然后我们将n1放到n2的位置,n2放到n3的位置，那么现在n1指向的是3,n2指向的是4，n3指向的是5 我们将n2的指向改变指向为n1     4->3->2->1->NULL

然后我们将n1放到n2的位置,n2放到n3的位置，那么现在n1指向的是4,n2指向的是5，n3指向的是走出去了 我们将n2的指向改变指向为n1     5->4->3->2->1->NULL

最后n1走到n2,n2走到n3    n2和n3都走出去了，现在的n1指向的是5的位置，那么现在的5就是新的头结点了


*/

class PalindromeList
{
public:
    ListNode*findMidNode(ListNode* phead)//封装一个函数来找中间节点
    {
        //快慢指针
        ListNode*slow=phead;
        ListNode*fast=phead;
        while(fast&&fast->next)//fast和fast下个节点不为空
        {
            slow=slow->next;//慢指针每次走一步
            fast=fast->next->next;//快指针每次走两次
        }
        //那么此时的slow节点刚好指向了中间节点
        return slow;

    }
    ListNode*reverseList(ListNode* phead)//封装一个函数来反转链表
    {
        ListNode*n1,*n2,*n3;
        n1=NULL;
        n2=phead;
        n3=n2->next;
        while(n2)//当n2为空的时候，那么此时的n1就指向的是反转后链表的头
        {
            n2->next=n1;
            n1=n2;
            n2=n3;
            if(n3)//n3不能为空才能往下走,只要n3到空了，我们就没必要让n3继续走了
            {
                n3=n3->next;
            }
        }
        //跳出循环 此时的n1就是反转后链表的头节点
        return n1;
    }
    bool chkPalindrome(ListNode* A)
    {
        //1.找中间节点
        ListNode*mid=findMidNode(A);//将链表A传过去


        //2.根据中间节点反转后面的链表
        ListNode*right=reverseList(mid);//将mid传过去，作为后半段头结点
        //那么此时的right就是指向的是反转后链表的头结点

        
        //3.从原链表和反转链表比较节点的值
        ListNode*left=A;//让left赋值为头节点
        //让right和left对应的指针进行一一比较
        while(right)//我们以right为主，一但right遍历到空，我们就没必要进行比较了
        {
            if(left->val!=right->val)//那么就不是回文结构了
            {
                return false;
            }
            //走到这里就说明当前节点对应的大小是相等的，那么我们就进行下一对节点的比较
            //让两个指针往后走
            left=left->next;
            right=right->next;
        }
        //跳出循环，那么此时的right已经为空了
        //那么这个链表的结构就是回文结构了
        return true;
    }




};