技术文摘
每日:链表倒数第 N 个结点的删除
2024-12-31 04:56:28 小编
每日:链表倒数第 N 个结点的删除
在数据结构与算法的世界中,链表是一种常见且重要的数据结构。而链表中倒数第 N 个结点的删除问题,是一个具有一定挑战性的操作。
让我们来理解一下这个问题。给定一个链表和一个整数 N,我们需要删除链表中倒数第 N 个结点。为了解决这个问题,我们可以使用双指针的方法。
我们设置两个指针,一个快指针和一个慢指针。快指针先向前移动 N 步,然后慢指针开始移动。当快指针到达链表末尾时,慢指针所指向的位置就是倒数第 N 个结点的前一个位置。
接下来,通过一些代码示例来更清晰地展示这个过程。以下是使用 C 语言实现的代码:
#include <stdio.h>
#include <stdlib.h>
// 链表节点结构体
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 创建新节点
ListNode* createNode(int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 删除倒数第 N 个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* fast = head;
ListNode* slow = head;
// 快指针先移动 N 步
for (int i = 0; i < n; i++) {
if (fast!= NULL) {
fast = fast->next;
} else {
return head;
}
}
// 同时移动,直到快指针到达末尾
while (fast->next!= NULL) {
fast = fast->next;
slow = slow->next;
}
// 删除倒数第 N 个节点
if (slow == head && fast->next == NULL) {
head = head->next;
} else {
ListNode* temp = slow->next;
slow->next = slow->next->next;
free(temp);
}
return head;
}
// 打印链表
void printList(ListNode* head) {
ListNode* curr = head;
while (curr!= NULL) {
printf("%d ", curr->val);
curr = curr->next;
}
printf("\n");
}
int main() {
ListNode* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
head->next->next->next->next = createNode(5);
int n = 2;
printf("原始链表: ");
printList(head);
head = removeNthFromEnd(head, n);
printf("删除倒数第 %d 个节点后的链表: ", n);
printList(head);
return 0;
}
这种方法的时间复杂度为 O(n),空间复杂度为 O(1),是一种比较高效的解决方案。
在实际应用中,链表倒数第 N 个结点的删除问题可能会出现在各种场景中,比如在处理动态数据、实现特定的逻辑流程等方面。熟练掌握这个问题的解决方法,对于提升我们的编程能力和解决实际问题的能力都具有重要意义。
通过巧妙地运用双指针的技巧,我们能够有效地解决链表倒数第 N 个结点的删除问题,为我们在数据结构和算法的领域中积累更多的经验和技巧。
- 鸿蒙系统自定义图标方法及样式修改
- 华为鸿蒙一键抠图的使用方法教程
- Ubuntu 利用 wine 安装 QQ 无法输入账号的解决办法
- Ubuntu 系统中 WPS 无法输入中文的解决办法
- 鸿蒙绑定电子身份证的方法
- Ubuntu 挂载移动硬盘时出现 exfat 文件系统类型未知错误
- 华为下载鸿蒙描述文件无法升级系统如何解决
- Ubuntu 磁盘空间快速释放的七种途径
- Ubuntu 系统中 IP 地址的设置方法
- Ubuntu Unity 切换应用程序窗口的快捷键使用方法
- 鸿蒙 OS 升级后卡顿、发热、耗电问题 华为官方解答
- 如何在 Ubuntu 中进入指定文件夹并更改路径
- 华为鸿蒙系统应用分身的设置方法
- 华为鸿蒙系统智慧助手的开启与关闭方法
- 鸿蒙系统音频输出设备的切换方法与技巧