如何用C语言精确地定义并操作一个包含整数的单链表L,并实现删除倒数第k个节点的功能?请提供完整的定义链表、创建链表、显示链表以及删除节点的函数代码,并解释其工作原理。若删除成功,函数应返回1,失败则返回0。同时,请给出相应的示例及功能测试的结果图。
时间: 2024-11-27 11:17:19 浏览: 12
C语言实现输出链表中倒数第k个节点
5星 · 资源好评率100%
在C语言中,我们可以使用结构体定义一个链表节点,然后通过指针来操作链表。以下是详细的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建一个新的链表节点
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode != NULL) {
newNode->data = value;
newNode->next = NULL;
return newNode;
}
printf("Memory allocation failed.\n");
return NULL;
}
// 插入节点到链表末尾
void appendNode(Node** head, int value) {
Node* newNode = createNode(value);
if (newNode == NULL) return;
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
// 显示链表
void displayList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// 删除倒数第k个节点(从0开始计数)
int deleteKthFromEnd(Node** head, int k) {
if (*head == NULL || k <= 0) {
printf("Invalid input or empty list.\n");
return 0;
}
Node* slow = *head;
Node* fast = *head;
// 使用快慢指针找到链表长度
for (int i = 0; fast && fast->next; i++) {
fast = fast->next;
if (i + 1 == k) {
break;
}
}
if (!fast || fast->next == NULL) {
return 0;
}
// 移除指定位置的节点
Node* prev = slow;
slow = slow->next;
while (slow != fast->next) {
prev = slow;
slow = slow->next;
}
prev->next = slow->next;
free(slow); // 释放已删除节点的内存
return 1; // 成功删除节点
}
// 测试示例
int main() {
Node* head = NULL;
appendNode(&head, 1);
appendNode(&head, 2);
appendNode(&head, 3);
appendNode(&head, 4);
appendNode(&head, 5);
printf("Original List: ");
displayList(head);
int k = 2;
if (deleteKthFromEnd(&head, k)) {
printf("After deleting %dkth node: ", k);
displayList(head);
} else {
printf("Failed to delete the %dkth node.\n", k);
}
return 0;
}
```
这个程序首先定义了链表节点结构,接着实现了创建节点、插入节点、显示链表和删除指定位置节点的函数。在`main`函数中,我们创建了一个简单的链表并演示了删除倒数第二个节点的操作。
当运行这个程序时,你会看到原始链表的内容(例如:1 2 3 4 5),然后删除倒数第二个节点(这里是4)后的结果(例如:1 2 3 5)。如果尝试删除不存在的位置的节点,会返回错误信息。
阅读全文