实现算法：删除倒数第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;
}

相关问题

linklist6-查询单链表倒数第k个链点的元素

### 回答1：
要实现单链表倒数第k个节点的元素，需要遍历整个链表，记录链表的长度，然后再从头开始遍历找到倒数第k个节点。可以使用两个指针，一个先走k步，然后另一个和它一起走，直到先走的那个指针走到链表尾部，此时后面的指针即为倒数第k个节点。

### 回答2：
单链表是一种比较常见的数据结构，在实际的编程中也经常会用到。而查询单链表倒数第k个链点的元素也是一道非常常见的面试题。

我们可以考虑利用双指针法来解决这个问题。具体步骤如下：

1.定义两个指针p和q，都指向单链表的头结点。

2.让指针p先移动k个位置，然后再让指针q开始从头结点开始逐个向后移动。

3.当指针p移动到链表的尾部时，此时q所指向的结点就是倒数第k个链点。

例如，我们有如下的一条单链表：1->2->3->4->5，如果要求查询倒数第2个链点的元素，那么我们可以按照上述方法进行操作：

1.让指针p先移动2个位置，指向的是数字3所在的结点。

2.此时让指针q开始逐个向后移动，当指针p到达链表尾部时，q所指向的结点就是倒数第2个链点，也就是数字4所在的结点。

3.最后返回数字4即可。

需要注意的是，在实际编程中，我们需要考虑一些特殊情况。例如，如果链表为空或者链表的长度小于k时，此时我们需要做出相应的异常处理。

总之，通过双指针法来查询单链表倒数第k个链点的元素，是一种简单、高效的解决方式。在实际的工作中，我们需要掌握这种基本的数据结构操作，并能够熟练运用。

### 回答3：
题目描述

给定一个单链表，请找出该链表倒数第k个链点的元素。

解题思路

遍历整个链表，记录链表长度len，然后再次从头遍历链表，当遍历到第len − k + 1个节点时，该节点就是我们要找的倒数第k个节点。

实现步骤

1. 定义两个指针pHead和pMove指向头结点，pMove向后移动k-1次。

2. 然后，同时移动pHead和pMove，直到pMove指向链表的末尾。

3. 移动后，pHead指向的就是倒数第k个节点。

需要注意的是：

1. k为0和链表为空时需要特殊处理。

2. 链表长度不足k的情况需要特殊处理。

3. 可以使用快慢指针来实现。

代码实现

C++实现

ListNode* FindKthToTail(ListNode* head, int k) {
if (head == nullptr || k == 0) return nullptr; //判断特殊情况
ListNode* slow = head;
ListNode* fast = head;
for (int i = 0; i < k - 1; ++i) {
if (fast->next != nullptr) {
fast = fast->next;
} else {
return nullptr; //链表长度不足k时返回nullptr
}
}
while (fast->next != nullptr) {
fast = fast->next;
slow = slow->next;
}
return slow; //返回倒数第k个节点
}

Python实现

class Solution:
def FindKthToTail(self, head: ListNode, k: int) -> ListNode:
if not head or k == 0:
return None # 判断特殊情况
slow, fast = head, head
for i in range(k - 1):
if fast.next:
fast = fast.next
else:
return None # 链表长度不足k时返回None
while fast.next:
fast, slow = fast.next, slow.next
return slow # 返回倒数第k个节点

时间复杂度

遍历链表两次，时间复杂度为O(n)。

空间复杂度

只需要定义两个指针，空间复杂度为O(1)。

总结

找到倒数第k个节点的元素是链表操作中比较常见的操作之一。使用这种方法可以遍历链表一次就找到倒数第k个节点，时间复杂度为O(n)，空间复杂度为O(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;
}

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