思路汇总，对初学者的我来说值得学习。
会慢慢学习和补充。
- 总言
- 单链表
- 1、力扣题：移除链表元素
- 思路一：
- 思路二：
- 思路三：
- 2、力扣题：反转单链表
- 思路一：头插法
- 思路二：双指针控制
- 3、力扣题：链表的中间结点
- 4、牛课题：链表中倒数第K个结点
- 思路一：
- 5、力扣题：合并两个有序链表
单链表
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;
}
题源：力扣题源
思路分析示意图：相当于头插，只不过需要注意是在原链表中插入（类比于数组原地调换）
代码：
/**
* 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指向尾结点
}
题源：力扣题源
思路示意图：
代码：
/**
* 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;
}
题源：牛客题源
思路示意图：
代码：本题的另一关键点在于考虑各种不满足情况，如：链表为空时、给定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}
题源：力扣题源
思路分析示意图：若不用并归的方法，另一个方法相当于在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;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）