C语言,给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
时间: 2024-03-13 09:35:37 浏览: 101
删除链表的倒数第 N 个结点.md
好的,我会帮您解决这个问题。下面是我给出的一种解法:
1. 首先创建两个指针,一个快指针和一个慢指针,初始时都指向链表的头结点。
2. 将快指针向后移动 n 步。
3. 然后同时移动快指针和慢指针,直到快指针指向链表的末尾节点。
4. 此时慢指针指向的节点即为要删除的倒数第 n 个节点的前一个节点。
5. 将慢指针指向的节点的 next 指针指向下一个节点的下一个节点,即跳过了要删除的节点。
6. 返回链表的头结点。
以下是使用 C 语言实现上述算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode *fast = head;
struct ListNode *slow = head;
// 快指针先向后移动 n 步
for (int i = 0; i < n; i++) {
fast = fast->next;
}
// 如果快指针为空,则说明要删除的是头结点
if (fast == NULL) {
return head->next;
}
// 快慢指针同时向后移动,直到快指针指向链表的末尾节点
while (fast->next != NULL) {
fast = fast->next;
slow = slow->next;
}
// 跳过要删除的节点
slow->next = slow->next->next;
return head;
}
// 测试代码
int main() {
// 创建链表
struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
head->val = 1;
struct ListNode *node1 = (struct ListNode *)malloc(sizeof(struct ListNode));
node1->val = 2;
head->next = node1;
struct ListNode *node2 = (struct ListNode *)malloc(sizeof(struct ListNode));
node2->val = 3;
node1->next = node2;
struct ListNode *node3 = (struct ListNode *)malloc(sizeof(struct ListNode));
node3->val = 4;
node2->next = node3;
struct ListNode *node4 = (struct ListNode *)malloc(sizeof(struct ListNode));
node4->val = 5;
node3->next = node4;
node4->next = NULL;
// 删除倒数第 2 个节点
int n = 2;
struct ListNode *newHead = removeNthFromEnd(head, n);
// 输出链表
while (newHead != NULL) {
printf("%d ", newHead->val);
newHead = newHead->next;
}
return 0;
}
```
希望能帮到你!如有疑问,请随时问我。
阅读全文