链表-删除倒数第k个节点

链表功能的实现-删除倒数第k个节点

(1)基本设计思想：
使用双指针法。初始化两个指针p和q，均指向头结点的下一个结点。首先让q指针先移动k-1次，若在此过程中q变为空，则说明链表长度不足k，返回0。否则，同时移动p和q，直到q为空。此时p指向的结点即为倒数第k个结点。

(2)详细实现步骤

1. 初始化first和second指向第一个数据结点。

2. 移动first指针k-1次，若中途first为空则返回0。

3. 同时移动first和second直到first下一个节点为空，此时p指向目标结点。

4. 输出结点数据并返回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;
}

运行结果