给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。
时间: 2024-03-13 18:25:11 浏览: 15
好的,这是一个技术问题,我可以回答。对于Delete Node in a Linked List问题,可以使用双指针算法来解决。首先先让快指针向后移动 n 次,然后将快指针和慢指针都往后移动,直到快指针到达链表尾部。此时慢指针正好指向要删除的节点,让慢指针的 next 指向慢指针的下下个节点即可。最后返回原链表的头节点。
相关问题
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
题目描述:
给定一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
思路:
使用双指针,先让第一个指针移动 n 个节点,然后同时移动两个指针,直到第一个指针到达链表末尾,此时第二个指针指向的节点就是要删除的节点。
代码实现:
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(); // 创建虚拟头节点
dummy->next = head;
ListNode* first = dummy;
ListNode* second = dummy;
for (int i = ; i < n; i++) {
first = first->next;
}
while (first->next != nullptr) {
first = first->next;
second = second->next;
}
ListNode* temp = second->next;
second->next = second->next->next;
delete temp;
return dummy->next;
}
};
C语言,给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
好的,我会帮您解决这个问题。下面是我给出的一种解法:
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;
}
```
希望能帮到你!如有疑问,请随时问我。