然后这里讲一下删倒数第k个元素的算法思想
我这里很简单啊,你要删倒数第k个,那不就是正数len-k+1个吗
举个例子:
比如12345
删倒数第3个,就是删正数5-3+1=3,也就是正数第3个
删倒数第2个,就是删正数5-2+1=4,也就是正数第4个
那么我知道要正数怎么删之后,我就找到要删结点的前一个也就是len-k个结点
然后就是很寻常的删除链表结点的操作了:“先连后断”
一些链表基本操作这里不多赘述,笔者有数据结构专栏进行了很详细的讲解
下面是代码:
先是准备工作
#define _CRT_SECURE_NO_WARNINGS
#include
//单链表定义
//链表结点
typedef struct {//定义单链表结点类型
int data;//数据域
struct LNode *next;//指针域
}LNode, *LinkList;
void MyPrint(LinkList L) {//打印链表元素
LNode* i = L->next;//用i指针遍历整个链表
while (i != NULL) {
printf("%d ", i->data);
i = i->next;
}
}
//尾插法建立单链表
LinkList List_TailInsert(LinkList* L) {
LNode*s;//新插入结点
int x;//结点值
*L = (LinkList)malloc(sizeof(LNode));
(*L)->next = NULL;
LNode* rear = *L;
//尾结点指针rear,这里赋值时注意对L解引用,L是指向头结点的指针,解引用才是头结点
int arr[10] = { 6,4,3,9,7,1,2,8,10,5};//初始链表元素
int i = 0;
while (i != 10) {//输入9999视为结束标志
s = (LNode*)malloc(sizeof(LNode));
s->data = arr[i];
s->next = NULL;
rear->next = s;
rear = s;
i++;
}
return L;
}
int length(LinkList L) {//获取链表长度
int len = 0;
LNode* p = L->next;
while (p != NULL) {
p = p->next;
len++;
}
return len;
}
然后就是该问题的解决函数及验证
void Del_k(LinkList* L, int k) {//删除链表倒数第k个元素
LNode*p = (*L)->next;
int len = length((*L));//获取L长度
//删倒数第k个,就是删正数第len-k+1个
//比如12345
//删倒数第3个,就是删正数5-3+1=3,也就是正数第三个
//删倒数第2个,就是删正数5-2+1=4,也就是正数第四个
int n = len - k ;//找到第len-k个元素,也就是len-k+1前面一个元素
for (int i = 1;i < n;i++) {//找到正数第len-k+1个
p = p->next;
}
LNode*q = p->next;//删q
p->next = q->next;
free(q);
}
int main() {
LinkList L = NULL;
List_TailInsert(&L);
printf("\n");
printf("初始链表为: ");
MyPrint(L);
int len = length(L);
printf("链表长度为%d", len);
int k = 0;
printf("\n");
printf("请输入要删倒数第几个元素: ");
scanf("%d", &k);
Del_k(&L,k);
printf("\n");
printf("删除倒数第k个元素后,链表为: ");
MyPrint(L);
}
删倒数第3个,也就是删这里的8
删倒数第7个,也就是删链表里的9