给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点,用C语言代码实现。
时间: 2023-08-10 12:55:17 浏览: 97
删除链表的倒数第 N 个结点.md
以下是用C语言实现删除链表倒数第n个节点的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
// 创建一个虚拟头结点,方便处理删除头结点的情况
struct ListNode dummy;
dummy.next = head;
struct ListNode *fast = &dummy;
struct ListNode *slow = &dummy;
// 快指针先走 n+1 步
for (int i = 0; i < n + 1; i++) {
fast = fast->next;
}
// 快慢指针同时向后移动,直到快指针到达链表末尾
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
// 删除倒数第 n 个节点
struct ListNode *temp = slow->next;
slow->next = slow->next->next;
free(temp);
return dummy.next; // 返回头结点
}
// 创建链表
struct ListNode* createLinkedList(int arr[], int n) {
if (n == 0) {
return NULL;
}
struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->val = arr[0];
head->next = NULL;
struct ListNode *cur = head;
for (int i = 1; i < n; i++) {
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = arr[i];
node->next = NULL;
cur->next = node;
cur = cur->next;
}
return head;
}
// 打印链表
void printLinkedList(struct ListNode *head) {
struct ListNode *cur = head;
while (cur != NULL) {
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
// 释放链表内存
void freeLinkedList(struct ListNode *head) {
struct ListNode *cur = head;
while (cur != NULL) {
struct ListNode *temp = cur;
cur = cur->next;
free(temp);
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = 2;
struct ListNode *head = createLinkedList(arr, sizeof(arr) / sizeof(arr[0]));
printf("原始链表:");
printLinkedList(head);
struct ListNode *result = removeNthFromEnd(head, n);
printf("删除倒数第%d个节点后的链表:", n);
printLinkedList(result);
freeLinkedList(result);
return 0;
}
```
这段代码中,我们使用快慢指针的方法来删除链表的倒数第n个节点。首先创建一个虚拟头结点(dummy),然后让快指针(fast)先向前移动n+1步,接着快慢指针同时向前移动,直到快指针到达链表末尾。此时慢指针(slow)指向的节点就是要删除的节点的前一个节点,我们通过修改指针的指向来删除该节点。最后返回虚拟头结点的next指针,即为删除倒数第n个节点后的链表的头结点。
注意,在使用完链表后,记得释放链表的内存,以避免内存泄漏。
阅读全文