1. 链表的回文结构
1.1 题目说明
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
1.2 题目分析
以下是对这道题目的分析：
一、题目要求
- 时间复杂度为 O(n)：意味着算法的执行时间与输入规模呈线性关系，不能随着输入规模的增大而增长过快。
- 额外空间复杂度为 O(1)：即除了输入所占用的空间外，算法所使用的额外空间不能随着输入规模的增大而增长过快，要保持在一个常量级别。
- 判断链表是否为回文结构：回文结构是指正序和逆序读取内容相同。
- 给定链表的头指针 A，返回一个 bool 值表示是否为回文结构，且链表长度小于等于 900。
二、知识点关联
5. 链表：链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。本题需要对链表进行遍历和操作。
6. 栈：栈是一种后进先出的数据结构，可以用来辅助判断链表是否为回文结构。例如，可以将链表的前半部分元素依次入栈，然后在遍历链表后半部分时与栈中的元素进行比较。
三、解题思路探讨
7. 由于时间复杂度要求为 O(n)，可以考虑一次遍历链表完成判断。
8. 额外空间复杂度为 O(1)，不能使用额外的数据结构来存储整个链表，需要巧妙地利用指针和变量来进行判断。
9. 可以使用快慢指针的方法找到链表的中间位置，然后对后半部分链表进行反转，再与前半部分进行比较来判断是否为回文结构。具体步骤如下：
- 使用两个指针，一个快指针每次移动两步，一个慢指针每次移动一步，当快指针到达链表末尾时，慢指针正好位于链表的中间位置。
- 如果链表长度为奇数，慢指针正好指向中间节点，此时可以忽略中间节点，继续对后半部分链表进行反转。
- 反转后半部分链表后，使用两个指针分别从链表的头部和中间位置（或中间位置的下一个节点）开始同时遍历，比较对应节点的值是否相等。如果在遍历过程中发现有不相等的节点，则说明链表不是回文结构；如果遍历完整个链表都没有发现不相等的节点，则说明链表是回文结构。
四、注意事项
10. 处理链表长度为奇数的情况时，要正确地找到中间节点并进行后续的操作。
11. 在反转链表后半部分时，要注意保存链表的结构，以便在判断完成后恢复链表的原始状态（如果需要的话）。
12. 考虑链表为空或只有一个节点的特殊情况，这种情况下链表显然是回文结构。
1.3 代码部分
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A)
{
//特殊情况的操作
if(A==NULL||A->next==NULL)//如果是空链表或者是一个节点的链表的话，那么肯定是回文结构的
{
return true;
}
//使用快慢指针找到链表的中间节点，最后停下来的时候慢指针就在中间节点上面
ListNode *slow=A;
ListNode *fast=A;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;//慢指针移动一步
fast=fast->next->next;//快指针移动两步
}
//2.反转链表的后半部分
ListNode *prev=NULL;
ListNode *cur=slow;//这个时候的slow在这个链表的中间节点，那么我们从中间节点反转后半部分
while(cur!=NULL)//从当前位置进行遍历后半部分的链表
{
//下面就是链表反装的代码，将后半部分链表进行反装的操作
ListNode *nexttmp=cur->next;//保存当前节点的下个节点
//下面两个代码是当前节点和前一个节点的转换操作
//当前节点的next指向我们的前一个节点
cur->next=prev;//将当前节点的指针反装，指向前一个节点，
prev=cur;//当前的节点变成了上一个节点了
cur=nexttmp;//更换当前的节点继续进行转换的操作，将后面剩下的节点进行转换操作
}
//这个时候我们的prev就变成了我们反转后连标记的头结点了
//3.接下来我们比较链表二档前半部分和反转后的后半部分
ListNode *firstHalf=A;//前半部分从链表头开始
ListNode* secondHalf = prev;//后半部分从反转链表的头结点开始
while(secondHalf != NULL)//比较每个节点，直到我们的反转链表部分遇到了空
{
if(firstHalf->val!=secondHalf->val)
{
return false;//如果两个节点的值对应不上的话，那么我们就可以判断这个链表不是回文的
}
//比较完成之后指针就往后移动了
firstHalf=firstHalf->next;
secondHalf = secondHalf->next;
}
//运行到这里，就说明我们的链表是回文的了，那么我们直接返回结果就行了
return true;
}
};
1.4 代码分析
我们先将特殊情况进行排除了 如果给我们的是一个空链表的话或者是一个节点的链表的话，那么这个肯定是回文结构的，我们直接返回true就行了
然后我们进行正常情况的分析
我们先利用快慢指针找到我们链表的中间节点，最后但我们的快指针停下来的时候我们的慢指针就在中间节点上面
当我们找到了中间节点的话，然后我们创建两个指针，prev指向我们的空，cur指向我们的慢指针当前的节点
我们这个题的思路就是找到中间节点，以中间节点为中心进行划分，将这个链表划分为两个链表，前半部分就是第一个链表，后半部分的反转版本就是我们的第二个链表
然后进行比较，如果对应的节点的值相等的话那么这个链表就是回文结构的
我们现在的cur指向我们的slow
然后我们从这个位置开始通过遍历将后半部分的链表进行翻转的操作
我们是对相邻的两个节点进行next指针的指向翻转操作，然后随着遍历，cur不断进行遍历
我们先创建一个指针tmp指向我们的当前节点的下一个节点，进行保存的操作，然后我们之间让当前指针的next指针指向我们的前一个节点，就是prev
进行完这两个节点的操作之后，我们进行遍历切换下一对节点
那么我们的当前节点就变成了prev了，就是prev指向我们的当前节点了，然后我们的cur变成了我们保存的tmp了，就是当前节点的下一个节点了，随着遍历的结束那么我们这个链表的后半部分就完成了翻转操作了，我们的prev就变成了头结点了
然后我们就进行我们的这个链表的两个部分进行比较操作了
还是定义两个指针进行遍历链表
我们比较每个节点对应的值
如果出现不相等的话，那么我们就可以判断这个链表就不是回文的结构了
我们直接返回false
如果循环结束的话，我们还没有返回的话，我们直接返回true，循环结束就可以判断我们的链表是回文的，两个部分节点的值都是相等的
思路总结：
1.先利用快慢指针让慢指针走到节点的中间
2.反转这个链表后面下半部分的节点
3.两个指针遍历两个部分，逐个比较里面存储的值是否相等
但是我们在这三个步骤之前我们需要分析下特殊的情况
比如链表为空的话或者链表值存在一个节点的话，这两种情况的话就属于回文结构吧了，我们直接返回true就行了
2. 链表分割
2.1 题目说明
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
2.2 题目分析
创建两个链表分别存储小于x和大于等于x的节点，最终将两个链表链接起来，形成一个规则重新排列的链表
我们既然不能改变节点的值，那么我们只能调整节点的指向了
1.创建两个链表，分别存储小于 x 和大于等于 x 的节点。
2.遍历原链表，将小于 x 的节点加入第一个链表，大于等于 x 的节点加入第二个链表。
3.将两个链表连接起来，注意处理尾指针的链接。
4.回新的链表头指针。
我们先创建两个链表的伪头结点，直接new出来，里面的值给到0：new ListNode(0)
创建好两个链表之后我们再创建指向两个链表的指针
然后我们在原链表中进行链表的遍历，逐个比较节点里面的val和x的大小，然后正确分配对应的链表
最后我们再将两个链表进行连接就行了
2.3 代码部分
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
/*
1.创建两个链表，分别存储小于 x 和大于等于 x 的节点。
2.遍历原链表，将小于 x 的节点加入第一个链表，大于等于 x 的节点加入第二个链表。
3.将两个链表连接起来，注意处理尾指针的链接。
4.回新的链表头指针。
因为不能改变节点的值，那么我们只能调整节点的相对位置了
*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x)
{
//创建两个链表的伪头结点
//伪头节点的作用是简化链表的插入操作，因为我们不需要为第一个节点单独处理，只要始终把节点插到伪头节点之后即可。
ListNode* smallerHead =new ListNode(0);//创建一个ListNode 类型的对象，传递参数 0 给它的构造函数，将节点的 val 值初始化为 0。
ListNode* largerHead = new ListNode(0);
//smallerHead是存储小于x的节点
//largerHead是存储大于等于x的节点
//定义两个指针指向这两个链表的尾部，方便添加节点
ListNode*smaller=smallerHead;
ListNode* larger = largerHead;
/*
smaller 和 larger 是指向当前链表尾部的指针，方便我们在链表中插入新的节点。
smaller 用于遍历 smallerHead 链表，指向存储小于 x 的节点的末尾。
larger 用于遍历 largerHead 链表，指向存储大于等于 x 的节点的末尾。*/
while(pHead!=nullptr)
{
if(pHead->val<x)//当前节点的值小于x的话,我们就将当前节点擦黑刀smaller链表的尾部
{
smaller->next=pHead;
smaller=smaller->next;//移动指针smaller,让他指向新的节点
}
else//当前节点的值大于x
{
larger->next=pHead;
larger=larger->next;//移动larger指向新的节点
}
pHead=pHead->next;//当前节点进行移动操作，遍历整个数组
}
//到这里的话就已经分好类了
//题目是将小的节点放到前面，那么大的节点就在后面，我们就需要将大节点的最后一个节点的next指向空
larger->next=nullptr;
//防止形成闭环，将最后一个节点指向空
//将小于x的链表和大于x的链表链接起来
smaller->next=largerHead->next;
//这里我们链接的是largerHead->next而不是largerHead,因为largerHead是伪头结点，不存储有效数据的
//返回新链表的头节点
return smallerHead->next;
2.4 代码分析
我们的思路是创建两个链表，分别存储大于x和小于x的节点
然后对原链表进行遍历，将对应的节点分别放到对应的链表中去
然后我们区分好大小节点的链表之后，我们将两个链表链接起来
最后我们将新的链表头结点返回了
那么我们先创建两个链表的哨兵位来占位置，分别是这两个指针，并且我们初始化的时候直接存放0这个数据，因为我们的哨兵位是不需要实际数据存放的
然后我们再创建两个指针指向我们这两个链表的尾节点，这个方便我们添加节点
然后我们就可以开始进行遍历了，使用while循环，循环条件是当前节点不是空的，然后我们就可以一直遍历下去
我们进行判断
将对应的节点放到对应的链表中去，判断完成之后我们进行当前节点的移动操作
然后出了循环，我们对应的数据都在对应的链表中了
大小链表都已经分好了，那么现在我们就将两个链表进行合并的操作
因为小的节点放到大节点之前
我们让小节点的尾指针指向我们的大节点链表的头结点，并且我们让大节点的尾节点指向空
我们这里的大节点链表的有效节点的是在哨兵位后面的那个节点，这里我们很容易指向错误
最后我返回新链表的结尾就行了，就是我们小链表的哨兵位的下个节点