总言
??思路汇总，对初学者的我来说值得学习。
??会慢慢学习和补充。
文章目录
??
单链表
??
1、力扣题：移除链表元素
??题源：力扣题源
??
思路一：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode*prev=NULL;
struct ListNode*cur=head;
while(cur)
{
//判断是否需要删除时
if(cur->val==val)
{
//头删
if(cur==head)
{
head=head->next;
free(cur);
cur=head;
}
//非头删
else{
prev->next=cur->next;
free(cur);
cur=prev->next;
}
}
else{
prev=cur;
cur=cur->next;
}
}
return head;
}
??
??
思路二：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode*cur=head;
struct ListNode*tail=NULL;
head=NULL;
while(cur)
{
if(cur->val==val)//删除操作
{
struct ListNode*del=cur;
cur=cur->next;//此步骤不能省去，故cur指针的变动在两种情景下需要分别写
free(del);
}
else//复刻操作:将有效数据尾插到新链表中
{
if(tail==NULL)//首次复刻
{
head=tail=cur;
}
else//非首次复刻
{
tail->next=cur;
tail=tail->next;//复刻后变动tail指针的指向位置
}
cur=cur->next;
tail->next=NULL;//每次操作后对于新建立的链表要将tail尾部next指向位置置空
}
}
return head;
}
??
??
思路三：
??对思路二的改进，加入一个哨兵位的结点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode*cur=head;
struct ListNode*tail=NULL;
//插入一个带哨兵位的结点
head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
tail->next=NULL;
while(cur)
{
if(cur->val==val)//删除操作
{
struct ListNode*del=cur;
cur=cur->next;//此步骤不能省去，故cur指针的变动在两种情景下需要分别写
free(del);
}
else//复刻操作:将有效数据尾插到新链表中
{
tail->next=cur;
tail=tail->next;//复刻后变动tail指针的指向位置
cur=cur->next;
tail->next=NULL;//每次操作后对于新建立的链表要将tail尾部next指向位置置空
}
}
//释放结点
struct ListNode* del=head->next;
free(head);
head=del;
return head;
}
??
??
2、力扣题：反转单链表
??题源：力扣题源
??
思路一：头插法
??思路分析示意图：相当于头插，只不过需要注意是在原链表中插入（类比于数组原地调换）
??代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
struct ListNode*cur=head;
struct ListNode*newhead=NULL;
while(cur)
{
//存储原链表cur后续结点
struct ListNode* next=cur->next;
//变动cur指向结点的链接关系
cur->next=newhead;
//头插变动头结点
newhead=cur;
//变动cur指向结点，完成遍历
cur=next;
}
return newhead;
}
??
思路二：双指针控制
??思路分析示意图：
??代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
//当链表为空的情况
if(head==NULL)
return NULL;
//确定初始指向关系：n1、n2用于改变原结点指向关系，n3用于找到断开后的结点
struct ListNode*n1,*n2,*n3;
n1=NULL;
n2=head;
n3=n2->next;
//链表不为空时
while(n2)//n2用于判断何时结束
{
//改变指向关系
n2->next=n1;
//改变指针迭代
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
//由于n2控制循环结束，当n2指向末尾结点时，用于下一次进入循环改变末结点，
//但此时n3已经指向空指针，故此处需要对此做处理
}
return n1;//注意此处返回值，结束循环时n2已经指向空指针，n1指向尾结点
}
??
??
3、力扣题：链表的中间结点
??题源：力扣题源
??思路示意图：
??代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head){
struct ListNode*fast,*slow;
fast=slow=head;
//判断结束条件：当fast指针指向末结点或指向某节点后的空指针时，循环结束，
//德摩根定律作用于布尔运算下，即得：当fast指针不为空且fast指针中next指针非空，则循环继续
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
??
??
4、牛课题：链表中倒数第K个结点
??题源：牛客题源
思路一：
??思路示意图：
??代码：本题的另一关键点在于考虑各种不满足情况，如：链表为空时、给定K值大于链表结点个数时,K=0时。所有这些边界问题都要考虑周全。
??另外关于两指针间的差值也不是限制于K，也可以用K-1，只要理清逻辑关系并注意边界问题即可。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
*
* @param pListHead ListNode类
* @param k int整型
* @return ListNode类
*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
if(pListHead==NULL)//用于防止链表为空时
return NULL;
struct ListNode*fast,*slow;
fast=slow=pListHead;
//调整两指针间距（相差K）：
int i=k;
while(i--)
{
if(fast)//用于防止给定k值大于链表实际个数
fast=fast->next;
else
return NULL;
}
//一对一挪动
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
??关于判断部分，也可以改写为如下情况：
//调整两指针间距（相差K）：
int i=k;
while((i--)&&(fast!=NULL))
{
// if(fast)//用于防止给定k值大于链表实际个数
fast=fast->next;
// else
// return NULL;
}
if(i>=0)
return NULL;
??此题中牛客测试用例：
用例输入：
1,{1,2,3,4,5}
5,{1,2,3,4,5}
100,{}
6,{1,2,3,4,5}
0,{1,2,3,4,5}
10,{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
预期输出：
{5}
{1,2,3,4,5}
{}
{}
{}
{11,12,13,14,15,16,17,18,19,20}
??
??
5、力扣题：合并两个有序链表
??题源：力扣题源
??思路分析示意图：若不用并归的方法，另一个方法相当于在pos位置处插入，只不过此方法思考起来需要注意插入位置判断条件。以List1为基链表，让List2在List1中pos位置插入，则判断条件为：list2指针所指向的数据小于list1指针指向数据时，在list1当前指针指向位置前插入。即它涉及到一个何时插入，插在前还是后的问题，需要根据自设的指针来分析判断。
??代码如下：上述思路只是针对常规情况，仍旧需要考虑一些边界问题。如：链表为空时.
??不带哨兵位，链表为空时要自行判断：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//链表为空时
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
struct ListNode*head,*cur;
head=cur=NULL;
//比较
while(list1&&list2)
{
//list1>list2时
if(list1->val>list2->val)
{
if(head==NULL)
{
head=cur=list2;
}
else
{
cur->next=list2;
cur=cur->next;
}
list2=list2->next;
}
else//list1<=list2时
{
if(head==NULL)
{
head=cur=list1;
}
else
{
cur->next=list1;
cur=cur->next;
}
list1=list1->next;
}
}
//剩余结点
if(list1)
{
cur->next=list1;
}
if(list2)
{
cur->next=list2;
}
return head;
}
??
??带哨兵位时，链表如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//创建一个带哨兵位的结点，哨兵位不存储有效数据
struct ListNode* head,*cur;
head=cur=(struct ListNode*)malloc(sizeof(struct ListNode));
cur->next=NULL;
//比较
while(list1&&list2)
{
//list1>list2时
if(list1->val>list2->val)
{
cur->next=list2;
cur=cur->next;
list2=list2->next;
}
else//list1<=list2时
{
cur->next=list1;
cur=cur->next;
list1=list1->next;
}
}
//剩余结点
if(list1)
{
cur->next=list1;
}
if(list2)
{
cur->next=list2;
}
//释放动态空间
struct ListNode* del=head;
head=head->next;
free(del);
//返回头结点
return head;
}
??
??
6、牛客题：链表分割
??题源：牛客题源
??大致思路分析：以X为分界线，创建两链表，一个保存小于X的结点，一个保存大于等于X的结点。遍历依次原链表，将符合要求的结点分别保存在新创建的两链表中，最后再将两链表拼接起来。
??此方法一个小关键点在于理清结点和链表的逻辑关系。比如结点尾插时，插入关系如何？再比如，遍历后对应新的两个链表而言，其中list指针此时指向什么位置？两链表链接在一起时，链接关系又是什么样的？（这些细节思考才是此题的关键问题）
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
if(pHead==NULL)//链表为空的情况
return NULL;
//创建两个新链表所需指针：每个链表需要对应的头指针及用于往后挪动的尾插指针
ListNode*list1,*list2,*cur,*head1,*head2;
cur=pHead;//原链表中用于遍历的指针
//两链表哨兵位的创建：（此题用哨兵位写代码比较方便）
list1=head1=(ListNode*)malloc(sizeof(ListNode));
list2=head2=(ListNode*)malloc(sizeof(ListNode));
list1->next=list2->next=NULL;
while(cur)
{
if(cur->val<x)//list1链表:用于链接小于X的结点
{
list1->next=cur;
list1=list1->next;
}
else//list2链表:用于链接大于等于X的结点
{
list2->next=cur;
list2=list2->next;
}
cur=cur->next;
}
//链接list1、list2：
if(head2->next)//list2中有原链表的结点时
{
list1->next=head2->next;
list2->next=NULL;
}
else//特殊情况之一：原链表所有结点都小于X，此时未用到list2链表，不必将其链接到list1后
list1->next=NULL;
//销毁哨兵位：
struct ListNode*del1,*del2;
del1=head1;del2=head2;
head1=head1->next;
free(del1);
free(del2);
return head1;
}
};
??
7、链表的回文结构
??题源：牛客题
??题目分析：回文结构就是对称结构。
??
??
??
??
??
??
??
