删除链表（删除链表倒数第n个元素）

## 删除链表### 简介链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。删除链表操作指的是从链表中移除一个或多个节点。### 删除链表的类型根据删除目标的不同，删除链表操作可以分为以下几种类型：

删除指定值的节点:

从链表中删除所有数据域等于特定值的节点。

删除指定位置的节点:

从链表中删除指定位置的节点，例如删除头节点、尾节点或第 k 个节点。

删除整个链表:

释放链表所有节点占用的内存空间。### 删除链表的方法#### 1. 删除指定值的节点删除指定值的节点通常需要遍历链表，找到目标节点并将其从链表中移除。

步骤：

1.

遍历链表:

从头节点开始，依次访问每个节点。 2.

查找目标节点:

对于每个节点，检查其数据域是否等于目标值。 3.

删除目标节点:

如果找到目标节点，则将其前一个节点的指针指向目标节点的下一个节点，并将目标节点的 `next` 指针设置为 `NULL`。

如果目标节点是头节点，则将头指针指向下一个节点。 4.

释放内存:

使用 `free()` 函数释放目标节点占用的内存空间。

代码示例 (C语言):

```c struct Node {int data;struct Node

next; };void deleteNode(struct Node

headRef, int key) {struct Node

temp =

headRef,

prev;// 如果头节点包含要删除的 keyif (temp != NULL && temp->data == key) {

headRef = temp->next; // 更改头指针free(temp); // 释放旧的头节点return;}// 遍历链表while (temp != NULL && temp->data != key) {prev = temp;temp = temp->next;}// 如果 key 不存在于链表中if (temp == NULL)return;// 从链表中取消链接节点prev->next = temp->next;free(temp); // 释放已删除节点 } ```#### 2. 删除指定位置的节点删除指定位置的节点需要先找到目标节点，然后将其从链表中移除。

步骤：

1.

找到目标节点:

如果要删除头节点，则直接将头指针指向下一个节点即可。

如果要删除其他位置的节点，则需要先遍历链表，找到目标节点的前一个节点。 2.

删除目标节点:

将目标节点前一个节点的 `next` 指针指向目标节点的下一个节点。

如果目标节点是尾节点，则将尾指针设置为 `NULL`。 3.

释放内存:

使用 `free()` 函数释放目标节点占用的内存空间。

代码示例 (C语言):

```c // 删除给定链表中指定位置的节点。 // position 是从 1 开始的，即 1 表示链表的第一个节点。 void deleteNodeAtPosition(struct Node

headRef, int position) {// 如果链表为空if (

headRef == NULL)return;// 存储头节点struct Node

temp =

headRef;// 如果要删除头节点if (position == 1) {

headRef = temp->next; // 更改头指针free(temp); // 释放旧的头节点return;}// 找到要删除节点的前一个节点// 我们需要遍历 position-1 个节点for (int i = 1; temp != NULL && i < position - 1; i++)temp = temp->next;// 如果 position 超过链表长度if (temp == NULL || temp->next == NULL)return;// temp->next 是要删除的节点。// 将下一个节点存储在 Node

next 中struct Node

next = temp->next->next;// 取消链接要删除的节点free(temp->next); // 释放要删除的节点temp->next = next; // 取消链接后重新链接 } ```#### 3. 删除整个链表删除整个链表需要遍历链表，并释放每个节点占用的内存空间。

步骤：

1.

遍历链表:

从头节点开始，依次访问每个节点。 2.

释放节点内存:

对于每个节点，使用 `free()` 函数释放其占用的内存空间。 3.

更新头指针:

将头指针设置为 `NULL`。

代码示例 (C语言):

```c void deleteList(struct Node

headRef) {struct Node

current =

headRef;struct Node

next;while (current != NULL) {next = current->next;free(current);current = next;}

headRef = NULL; } ```### 总结删除链表是链表操作中的基本操作之一。根据删除目标的不同，可以选择不同的方法来删除链表。在实际应用中，需要根据具体的需求选择合适的删除方法。

删除链表

简介链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。删除链表操作指的是从链表中移除一个或多个节点。

删除链表的类型根据删除目标的不同，删除链表操作可以分为以下几种类型：* **删除指定值的节点:** 从链表中删除所有数据域等于特定值的节点。 * **删除指定位置的节点:** 从链表中删除指定位置的节点，例如删除头节点、尾节点或第 k 个节点。 * **删除整个链表:** 释放链表所有节点占用的内存空间。

删除链表的方法

1. 删除指定值的节点删除指定值的节点通常需要遍历链表，找到目标节点并将其从链表中移除。**步骤：**1. **遍历链表:** 从头节点开始，依次访问每个节点。 2. **查找目标节点:** 对于每个节点，检查其数据域是否等于目标值。 3. **删除目标节点:*** 如果找到目标节点，则将其前一个节点的指针指向目标节点的下一个节点，并将目标节点的 `next` 指针设置为 `NULL`。* 如果目标节点是头节点，则将头指针指向下一个节点。 4. **释放内存:** 使用 `free()` 函数释放目标节点占用的内存空间。**代码示例 (C语言):**```c struct Node {int data;struct Node* next; };void deleteNode(struct Node** headRef, int key) {struct Node* temp = *headRef, *prev;// 如果头节点包含要删除的 keyif (temp != NULL && temp->data == key) {*headRef = temp->next; // 更改头指针free(temp); // 释放旧的头节点return;}// 遍历链表while (temp != NULL && temp->data != key) {prev = temp;temp = temp->next;}// 如果 key 不存在于链表中if (temp == NULL)return;// 从链表中取消链接节点prev->next = temp->next;free(temp); // 释放已删除节点 } ```

2. 删除指定位置的节点删除指定位置的节点需要先找到目标节点，然后将其从链表中移除。**步骤：**1. **找到目标节点:*** 如果要删除头节点，则直接将头指针指向下一个节点即可。* 如果要删除其他位置的节点，则需要先遍历链表，找到目标节点的前一个节点。 2. **删除目标节点:*** 将目标节点前一个节点的 `next` 指针指向目标节点的下一个节点。* 如果目标节点是尾节点，则将尾指针设置为 `NULL`。 3. **释放内存:** 使用 `free()` 函数释放目标节点占用的内存空间。**代码示例 (C语言):**```c // 删除给定链表中指定位置的节点。 // position 是从 1 开始的，即 1 表示链表的第一个节点。 void deleteNodeAtPosition(struct Node** headRef, int position) {// 如果链表为空if (*headRef == NULL)return;// 存储头节点struct Node* temp = *headRef;// 如果要删除头节点if (position == 1) {*headRef = temp->next; // 更改头指针free(temp); // 释放旧的头节点return;}// 找到要删除节点的前一个节点// 我们需要遍历 position-1 个节点for (int i = 1; temp != NULL && i < position - 1; i++)temp = temp->next;// 如果 position 超过链表长度if (temp == NULL || temp->next == NULL)return;// temp->next 是要删除的节点。// 将下一个节点存储在 Node *next 中struct Node* next = temp->next->next;// 取消链接要删除的节点free(temp->next); // 释放要删除的节点temp->next = next; // 取消链接后重新链接 } ```

3. 删除整个链表删除整个链表需要遍历链表，并释放每个节点占用的内存空间。**步骤：**1. **遍历链表:** 从头节点开始，依次访问每个节点。 2. **释放节点内存:** 对于每个节点，使用 `free()` 函数释放其占用的内存空间。 3. **更新头指针:** 将头指针设置为 `NULL`。**代码示例 (C语言):**```c void deleteList(struct Node** headRef) {struct Node* current = *headRef;struct Node* next;while (current != NULL) {next = current->next;free(current);current = next;}*headRef = NULL; } ```

总结删除链表是链表操作中的基本操作之一。根据删除目标的不同，可以选择不同的方法来删除链表。在实际应用中，需要根据具体的需求选择合适的删除方法。