实现算法：删除倒数第k个结点 int deleteK(LinkList head,int k)

//定义结点类型
typedef struct Node {
int data;
struct Node *next;
}Node, *LinkList;

//删除倒数第k个结点函数
int deleteK(LinkList head, int k) {
//定义两个指针，p和q，p先向前k个结点
Node *p = head, *q = head;
int count = 0;
while (p != NULL && count < k) {
p = p->next;
count++;
}
//p为空，说明链表长度小于k，返回0
if (p == NULL) {
return 0;
}
//q和p同时向前，直到p指向结尾节点
while (p->next != NULL) {
q = q->next;
p = p->next;
}
//删除倒数第k个结点
Node *temp = q->next;
q->next = temp->next;
free(temp);
return 1;
}

相关问题

补全以下函数：//删除指定结点 bool DeleteNode(LinkList L, LNode* p) { }

### 回答1：
bool DeleteNode(LinkList L, LNode* p) {
if (L == nullptr || p == nullptr) {
return false;
}
// 找到p结点的前驱结点q
LNode* q = L;
while (q->next != p) {
q = q->next;
if (q == nullptr) {
return false;
}
}
// 删除p结点
q->next = p->next;
free(p);
return true;
}

### 回答2：
补全以下函数：

//删除指定结点
bool DeleteNode(LinkList L, LNode* p) {
if(L == NULL || p == NULL) {
return false; //链表为空或指定结点为空，删除失败
}

//判断要删除的结点是不是头结点
if(L == p) {
L = L->next; //将头结点指向下一个结点
free(p); //释放要删除的结点的内存空间
return true;
}

LNode* prev = L; //保存前一个结点
while(prev->next != p && prev->next != NULL) {
prev = prev->next; //找到要删除结点的前一个结点
}

if(prev->next == NULL) {
return false; //没有找到要删除的结点，删除失败
}

prev->next = p->next; //将前一个结点指向要删除结点的下一个结点
free(p); //释放要删除的结点的内存空间

return true;
}

### 回答3：
补全以下函数：

bool DeleteNode(LinkList L, LNode* p) {
if (L == NULL || p == NULL) { // 判断链表和指定结点是否为空
return false; // 若为空则删除失败
}

if (L == p) { // 若删除的结点为头结点
L = L->next; // 将头结点后移一位
free(p); // 释放删除结点的内存空间
return true;
}

LNode* preNode = L; // 声明一个指向前一个结点的指针
while (preNode->next != NULL && preNode->next != p) {
preNode = preNode->next; // 查找指定结点的前一个结点
}

if (preNode->next == NULL) { // 若找不到指定结点
return false; // 删除失败
}

preNode->next = p->next; // 将前一个结点的指针指向删除结点的下一个结点
free(p); // 释放删除结点的内存空间
return true;
}

这个函数的功能是从单链表中删除指定结点。首先判断链表和指定结点是否为空，如果为空，则删除失败。接着判断要删除的结点是否为头结点，如果是，则将链表的头指针后移一位，释放删除结点的内存空间，返回删除成功。如果不是头结点，则需要查找指定结点的前一个结点，将前一个结点的指针指向删除结点的下一个结点，然后释放删除结点的内存空间，返回删除成功。如果找不到指定结点，则删除失败。

c语言 数据结构 设有头结点单链表，删除单链表中倒数第k个结点。第一行输入若干个整数建立带头结点的单链表，以e结尾。 第二行输入一个整数k，表示删除倒数第k个结点。输出删除后单链表的所有元素。

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *LinkList;

LinkList createList() {
    LinkList head = (LinkList) malloc(sizeof(Node));
    head->next = NULL;
    LinkList p = head;
    ElemType x;
    scanf("%d", &x);
    while (x != -1) {
        LinkList newNode = (LinkList) malloc(sizeof(Node));
        newNode->data = x;
        newNode->next = NULL;
        p->next = newNode;
        p = newNode;
        scanf("%d", &x);
    }
    return head;
}

void printList(LinkList head) {
    LinkList p = head->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void deleteKthFromEnd(LinkList head, int k) {
    LinkList p = head->next, q = head->next, pre = head;
    int cnt = 0;
    while (q && cnt < k) {
        q = q->next;
        cnt++;
    }
    while (q) {
        p = p->next;
        q = q->next;
        pre = pre->next;
    }
    pre->next = p->next;
    free(p);
}

int main() {
    LinkList list = createList();
    int k;
    scanf("%d", &k);
    deleteKthFromEnd(list, k);
    printList(list);
    return 0;
}