链表-删除倒数第k个节点
链表功能的实现-删除倒数第k个节点(1)基本设计思想：
使用双指针法。初始化两个指针p和q，均指向头结点的下一个结点。首先让q指针先移动k-1次，若在此过程中q变为空，则说明链表长度不足k，返回0。否则，同时移动p和q，直到q为空。此时p指向的结点即为倒数第k个结点。
(2)详细实现步骤
[*]初始化first和second指向第一个数据结点。
[*]移动first指针k-1次，若中途first为空则返回0。
[*]同时移动first和second直到first下一个节点为空，此时p指向目标结点。
[*]输出结点数据并返回1。
(3)算法实现
/*****************************************************
* file name:sequencelist.c
* author :zzlyx1239@126.com
* date :2025.3.10
* brief :单链表顺序存储
* note :none
*
* Copyright (c) 2025 zzlyx1239@126.com All Right Reserved
*
*******************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//将int类型重命名为DataType
typedef int DataType_t;
//定义一个链式存储的顺序表，声明顺序表中的数据类型、指针
typedef struct LinkList
{
DataType_t data;//定义链式存储中的数据部分
struct LinkList *next;//定义指向后继元素的指针
}LList_t;
//创建一个链表，并初始化
LList_t *LinkList_Creat(void)
{
//1.为头节点申请堆内存空间
LList_t *Head=(LList_t *)calloc(1,sizeof(LList_t));
if(Head==NULL)
{
perror("calloc for Head is Failed!!!");
exit(-1);//异常退出
}
//2.申请成功，进行初始化
Head->next=NULL;
return Head;
}
//创建新节点并初始化
LList_t *LList_NewNode(DataType_t data)
{
//为新节点申请内存空间
LList_t *New=(LList_t*)calloc(1,sizeof(LList_t));
if(New==NULL)
{
perror("calloc for newnode memory is failed!!!");
return NULL;
}
//对新节点进行初始化
New->data=data;
New->next=NULL;
return New;
}
//向链表中插入新的元素，头插法
bool LList_HeadAdd(LList_t *Head,DataType_t e)
{
//调用创建新节点的函数来创建新节点
LList_t *New=LList_NewNode(e);
if(NULL==New)
{
perror("cannot add new node!!!");
return false;
}
//如果头节点后面没有节点
if(Head->next==NULL)
{
Head->next=New;
return true;
}
New->next=Head->next;
Head->next=New;
return true;
}
//尾插法
bool LList_TailInsert(LList_t *Head,DataType_t e)
{
//调用创建新节点的函数来创建新节点
LList_t* New=LList_NewNode(e);
if(NULL==New)
{
perror("cannot add new node!!!");
return false;
}
//如果头节点后面没有节点，直接插入即可
if(Head->next==NULL)
{
Head->next=New;
return true;
}
//遍历到最后一个节点
LList_t *Phead = Head;
while(Phead->next)
{
Phead=Phead->next;
}
Phead->next=New;
return true;
}
//头删
bool LList_HeadDel(LList_t *Head)
{
//备份首节点
LList_t* Phead=Head->next;
//判断链表是否为空，如果为空则删除失败
if(Head->next==NULL)
{
printf("Linklist is Empty!!!");
return false;
}
//链表非空，删除首届点
Head->next=Phead->next;
Phead->next=NULL;
//释放首节点
free(Phead);
return true;
}
//设计一个算法，删除单链表中最小值节点
bool LList_DelMin(LList_t *Head)
{
LList_t *Min_Prev;
LList_t *Min=Head->next;//假设最小值节点为首节点
LList_t *Phead=Head->next;//记录首节点地址
//遍历链表找到最小值节点
while(Phead->next)
{
if(Min->data>Phead->next->data)
{
Min_Prev=Phead;//将最小节点前驱给Min_Prev
Min=Phead->next;//将最小节点给Min
}
Phead=Phead->next;
}
//删除最小值节点
Min_Prev->next=Phead->next;
Min->next=NULL;
free(Min);
return true;
}
//删除链表中倒数第k个节点，成功返回1并输出节点data值，失败返回0
DataType_t LList_DelKNode(LList_t *Head,unsigned int k)
{
//1.定义两个节点记录指针移动
LList_t *LList_First=Head->next;//first节点:首节点
LList_t *LList_Second=Head->next;//second节点:首节点
LList_t *Second_prev=Head;//记录second节点的前驱节点
//2.检查列表是否为空
if(Head->next==NULL)
{
printf("LinkList is empty!!!");
return 0;
}
//3.先让first节点向后移动k-1,并且first节点不能是NULL
for(int i=1;i<=k-1;i++)
{
LList_First=LList_First->next;
if(LList_First==NULL)
{
return false;
}
}
//3.让Second节点与First节点一起移动，直到First—>next=NULL
while(LList_First->next)
{
LList_First=LList_First->next;
LList_Second=LList_Second->next;
Second_prev=Second_prev->next;
}
//此时Second节点即是倒数第k个节点，删除Second节点
printf("倒数第%d个节点的值为：%d\n",k,LList_Second->data);
Second_prev->next=LList_Second->next;
LList_Second->next==NULL;
free(LList_Second);//释放删除节点的空间
return 0;
}
//遍历
void LList_Print(LList_t *Head)
{
//对链表的头文件的地址进行备份
LList_t *Phead = Head;
//首结点
while(Phead->next)
{
//把头的直接后继作为新的头结点
Phead = Phead->next;
//输出头结点的直接后继的数据域
printf("data = %d\n",Phead->data);
}
}
int main()
{
//创建链表
LList_t *Head=LinkList_Creat();
//向链表中插入新节点
LList_HeadAdd(Head,1);
LList_HeadAdd(Head,2);
LList_HeadAdd(Head,5);
LList_HeadAdd(Head,6);
LList_HeadAdd(Head,8);
LList_HeadAdd(Head,4);
LList_HeadAdd(Head,16);
LList_HeadAdd(Head,39);
LList_HeadAdd(Head,46);
//遍历输出
LList_Print(Head);
printf("\n");
//删除 头删
LList_HeadDel(Head);
LList_Print(Head);
printf("\n");
//删除最小值节点
LList_DelMin(Head);
LList_Print(Head);
printf("\n");
//删除倒数第k个节点
LList_DelKNode(Head,3);
LList_Print(Head);
return 0;
}运行结果
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]