链表-删除倒数第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)算法实现

1. /*****************************************************
2. *   file name:sequencelist.c
3. *   author   :zzlyx1239@126.com
4. *   date     :2025.3.10
5. *   brief    :单链表顺序存储
6. *   note     :none
7. *
8. *   Copyright (c) 2025 zzlyx1239@126.com All Right Reserved
9. *
10. *******************************************************/
12. #include <stdio.h>
13. #include <stdbool.h>
14. #include <stdlib.h>
16. //将int类型重命名为DataType
17. typedef int DataType_t;
19. //定义一个链式存储的顺序表，声明顺序表中的数据类型、指针
20. typedef struct LinkList
21. {
22.     DataType_t      data;//定义链式存储中的数据部分
23.     struct LinkList *next;//定义指向后继元素的指针
24. }LList_t;
26. //创建一个链表，并初始化
27. LList_t *LinkList_Creat(void)
28. {
29.     //1.为头节点申请堆内存空间
30.     LList_t *Head=(LList_t *)calloc(1,sizeof(LList_t));
31.     if(Head==NULL)
32.     {
33.         perror("calloc for Head is Failed!!!");
34.         exit(-1);//异常退出
35.     }
36.    
37.     //2.申请成功，进行初始化
38.     Head->next=NULL;
39.     return Head;
40. }
42. //创建新节点并初始化
43. LList_t *LList_NewNode(DataType_t data)
44. {
45.     //为新节点申请内存空间
46.     LList_t *New=(LList_t*)calloc(1,sizeof(LList_t));
47.     if(New==NULL)
48.     {
49.         perror("calloc for newnode memory is failed!!!");
50.         return NULL;
51.     }
52.     //对新节点进行初始化
53.     New->data=data;
54.     New->next=NULL;
55.     return New;
56. }
58. //向链表中插入新的元素，头插法
59. bool LList_HeadAdd(LList_t *Head,DataType_t e)
60. {
61.     //调用创建新节点的函数来创建新节点
62.     LList_t *New=LList_NewNode(e);
63.     if(NULL==New)
64.     {
65.         perror("cannot add new node!!!");
66.         return false;
67.     }
68.     //如果头节点后面没有节点
69.     if(Head->next==NULL)
70.     {
71.         Head->next=New;
72.         return true;
73.     }
74.     New->next=Head->next;
75.     Head->next=New;
76.     return true;
77. }
79. //尾插法
80. bool LList_TailInsert(LList_t *Head,DataType_t e)
81. {
82.     //调用创建新节点的函数来创建新节点
83.     LList_t* New=LList_NewNode(e);
84.     if(NULL==New)
85.     {
86.         perror("cannot add new node!!!");
87.         return false;
88.     }
89.     //如果头节点后面没有节点，直接插入即可
90.     if(Head->next==NULL)
91.     {
92.         Head->next=New;
93.         return true;
94.     }
95.     //遍历到最后一个节点
96.     LList_t *Phead = Head;
97.     while(Phead->next)
98.     {
99.         Phead=Phead->next;
100.     }
101.     Phead->next=New;
102.     return true;
103. }
106. //头删
107. bool LList_HeadDel(LList_t *Head)
108. {
109.     //备份首节点
110.     LList_t* Phead=Head->next;
111.     //判断链表是否为空，如果为空则删除失败
112.     if(Head->next==NULL)
113.     {
114.         printf("Linklist is Empty!!!");
115.         return false;
116.     }
118.     //链表非空，删除首届点
119.     Head->next=Phead->next;
120.     Phead->next=NULL;
121.     //释放首节点
122.     free(Phead);
123.     return true;
124. }
127. //设计一个算法，删除单链表中最小值节点
128. bool LList_DelMin(LList_t *Head)
129. {
130.     LList_t *Min_Prev;
131.     LList_t *Min=Head->next;//假设最小值节点为首节点
132.     LList_t *Phead=Head->next;//记录首节点地址
133.     //遍历链表找到最小值节点
134.     while(Phead->next)
135.     {
136.         if(Min->data>Phead->next->data)
137.         {
138.             Min_Prev=Phead;//将最小节点前驱给Min_Prev
139.             Min=Phead->next;//将最小节点给Min
140.         }
141.         Phead=Phead->next;
142.     }
144.     //删除最小值节点
145.     Min_Prev->next=Phead->next;
146.     Min->next=NULL;
147.     free(Min);
148.     return true;
149. }
151. //删除链表中倒数第k个节点，成功返回1并输出节点data值，失败返回0
152. DataType_t LList_DelKNode(LList_t *Head,unsigned int k)
153. {
154.     //1.定义两个节点记录指针移动
155.     LList_t *LList_First=Head->next;//first节点:首节点
156.     LList_t *LList_Second=Head->next;//second节点:首节点
157.     LList_t *Second_prev=Head;//记录second节点的前驱节点
158.     //2.检查列表是否为空
159.     if(Head->next==NULL)
160.     {
161.         printf("LinkList is empty!!!");
162.         return 0;
163.     }
164.     //3.先让first节点向后移动k-1,并且first节点不能是NULL
165.     for(int i=1;i<=k-1;i++)
166.     {
167.         LList_First=LList_First->next;
168.         if(LList_First==NULL)
169.         {
170.             return false;
171.         }
172.     }
173.     //3.让Second节点与First节点一起移动，直到First—>next=NULL
174.     while(LList_First->next)
175.     {
176.         LList_First=LList_First->next;
177.         LList_Second=LList_Second->next;
178.         Second_prev=Second_prev->next;
179.     }
180.     //此时Second节点即是倒数第k个节点，删除Second节点
181.     printf("倒数第%d个节点的值为：%d\n",k,LList_Second->data);
182.     Second_prev->next=LList_Second->next;
183.     LList_Second->next==NULL;
184.     free(LList_Second);//释放删除节点的空间
185.     return 0;
186. }
189. //遍历
190. void LList_Print(LList_t *Head)
191. {
192.         //对链表的头文件的地址进行备份
193.         LList_t *Phead = Head;
194.        
195.         //首结点
196.         while(Phead->next)
197.         {
198.                 //把头的直接后继作为新的头结点
199.                 Phead = Phead->next;
201.                 //输出头结点的直接后继的数据域
202.                 printf("data = %d\n",Phead->data);
203.         }
205. }
208. int main()
209. {
210.     //创建链表
211.     LList_t *Head=LinkList_Creat();
212.     //向链表中插入新节点
213.     LList_HeadAdd(Head,1);
214.     LList_HeadAdd(Head,2);
215.     LList_HeadAdd(Head,5);
216.     LList_HeadAdd(Head,6);
217.     LList_HeadAdd(Head,8);
218.     LList_HeadAdd(Head,4);
219.     LList_HeadAdd(Head,16);
220.     LList_HeadAdd(Head,39);
221.     LList_HeadAdd(Head,46);
223.     //遍历输出
224.     LList_Print(Head);
225.     printf("\n");
226.     //删除 头删
227.     LList_HeadDel(Head);
228.     LList_Print(Head);
229.     printf("\n");
230.     //删除最小值节点
231.     LList_DelMin(Head);
232.     LList_Print(Head);
233.     printf("\n");
234.     //删除倒数第k个节点
235.     LList_DelKNode(Head,3);
236.     LList_Print(Head);
237.     return 0;
238. }

复制代码

运行结果

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。