用C语言设计一个足够高效的算法,删除单链表L的倒数第k个元素。
时间: 2024-09-27 20:11:11 浏览: 37
在C语言中,设计一个删除单链表L的倒数第k个元素的高效算法,你可以使用双指针法。这里有一个简单的实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 删除倒数第k个节点
Node* deleteKthFromList(Node* head, int k) {
if (head == NULL || k <= 0 || head->next == NULL) {
return head;
}
// 初始化两个指针,快慢指针
Node* slow = head;
Node* fast = head;
// 快速指针前进k个位置
for (int i = 0; i < k; ++i) {
if (fast != NULL) {
fast = fast->next;
} else {
return head; // 如果链表长度小于k,提前返回
}
}
// 慢速指针同步,直到快指针到达链表尾部
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
}
}
// 删除倒数第k个节点
if (slow != NULL) {
slow->next = slow->next->next;
}
return head;
}
// 测试函数
void printList(Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
// 创建链表并插入节点
Node* list = createLinkedList(); // 自行实现链表创建函数
// ...
// 删除倒数第k个元素
list = deleteKthFromList(list, k); // k是你想要删除的元素位置
// 打印修改后的链表
printList(list);
return 0;
}
```
这里的算法时间复杂度是O(n),其中n是链表的长度,因为我们需要遍历链表两次。空间复杂度是O(1),因为我们只用了几个额外的指针变量。
阅读全文