6-10 单链表结点删除

单链表结点删除的基本思路是找到要删除的结点的前一个结点，然后将它的 next 指针指向要删除结点的下一个结点。

具体操作步骤如下：

1. 找到要删除的结点的前一个结点，假设为 preNode。
2. 将 preNode 的 next 指针指向要删除结点的下一个结点，假设为 delNode。
3. 释放要删除的结点 delNode。

以下是 C++ 代码示例：

void deleteNode(ListNode* head, int val) {
    ListNode* preNode = head;
    ListNode* delNode = head->next;
    while (delNode != nullptr && delNode->val != val) {
        preNode = delNode;
        delNode = delNode->next;
    }
    if (delNode != nullptr) {
        preNode->next = delNode->next;
        delete delNode;
    }
}

以上代码中，我们假设头结点为 head，要删除的结点的值为 val。首先从头结点开始遍历链表，找到要删除的结点的前一个结点 preNode 和要删除的结点 delNode。然后将 preNode 的 next 指针指向 delNode 的下一个结点，最后释放 delNode 的内存空间。

相关问题

（1）创建一个带头结点的单链表。 要求：此单链表长度为10；创建完成后，输出显示所创建单链表各结点的值。 （2）实现单链表的插入，并显示完成插入后单链表各结点的值。 要求：插入一个新的结点，其值为27，成为单链表的第5个结点；插入完成后，输出显示此时单链表的长度以及各结点的值。 （3）实现单链表的删除，完成删除后，输出单链表各结点的值。 （4）编程实现单链表的查找。

以下是Python语言的实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 创建一个带头结点的单链表
head = ListNode(-1)
cur = head
for i in range(10):
    cur.next = ListNode(i)
    cur = cur.next

# 输出单链表各结点的值
cur = head.next
while cur:
    print(cur.val, end=' ')
    cur = cur.next
print()

# 在第5个结点处插入新节点
new_node = ListNode(27)
cur = head
for i in range(4):
    cur = cur.next
new_node.next = cur.next
cur.next = new_node

# 输出插入后单链表各结点的值
cur = head.next
while cur:
    print(cur.val, end=' ')
    cur = cur.next
print()

# 删除第5个结点
cur = head
for i in range(4):
    cur = cur.next
cur.next = cur.next.next

# 输出删除后单链表各结点的值
cur = head.next
while cur:
    print(cur.val, end=' ')
    cur = cur.next
print()

# 查找值为3的结点
cur = head.next
while cur:
    if cur.val == 3:
        print("找到值为3的结点")
        break
    cur = cur.next
else:
    print("未找到值为3的结点")

输出：

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 27 4 5 6 7 8 9 
0 1 2 3 27 5 6 7 8 9 
找到值为3的结点

请用C++写出（1）创建一个带头结点的单链表。 要求：此单链表长度为10；创建完成后，输出显示所创建单链表各结点的值。 （2）实现单链表的插入，并显示完成插入后单链表各结点的值。 要求：插入一个新的结点，其值为27，成为单链表的第5个结点；插入完成后，输出显示此时单链表的长度以及各结点的值。 （3）实现单链表的删除，完成删除后，输出单链表各结点的值。 （4）编程实现单链表的查找。 要求：如果查找成功，程序能够输出显示该结点位置信息；如果查找失败，程序应显示“该单链表中无此数据元素”信息。的代码

以下是C++代码实现：

#include <iostream>
using namespace std;

//定义单链表结点结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

//创建带头结点的单链表
ListNode* createList() {
    ListNode *head = new ListNode(0);
    ListNode *cur = head;
    for (int i = 1; i <= 10; i++) {
        ListNode *node = new ListNode(i);
        cur->next = node;
        cur = cur->next;
    }
    return head;
}

//输出单链表各结点的值
void printList(ListNode *head) {
    ListNode *cur = head->next;
    while (cur) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

//单链表插入
void insertNode(ListNode *head, int val, int pos) {
    ListNode *cur = head;
    for (int i = 1; i < pos; i++) {
        if (cur == NULL) {
            cout << "插入位置无效" << endl;
            return;
        }
        cur = cur->next;
    }
    ListNode *node = new ListNode(val);
    node->next = cur->next;
    cur->next = node;
}

//单链表删除
void deleteNode(ListNode *head, int val) {
    ListNode *cur = head;
    while (cur->next && cur->next->val != val) {
        cur = cur->next;
    }
    if (cur->next == NULL) {
        cout << "该单链表中无此数据元素" << endl;
        return;
    }
    ListNode *temp = cur->next;
    cur->next = temp->next;
    delete temp;
}

//单链表查找
int searchNode(ListNode *head, int val) {
    int pos = 1;
    ListNode *cur = head->next;
    while (cur && cur->val != val) {
        pos++;
        cur = cur->next;
    }
    if (cur == NULL) {
        cout << "该单链表中无此数据元素" << endl;
        return -1;
    } else {
        cout << "该结点的位置为：" << pos << endl;
        return pos;
    }
}

int main() {
    ListNode *head = createList();
    cout << "初始单链表各结点的值为：" << endl;
    printList(head);
    insertNode(head, 27, 5);
    cout << "插入后的单链表各结点的值为：" << endl;
    printList(head);
    deleteNode(head, 5);
    cout << "删除后的单链表各结点的值为：" << endl;
    printList(head);
    searchNode(head, 3);
    searchNode(head, 15);
    return 0;
}

输出结果：

初始单链表各结点的值为：
1 2 3 4 5 6 7 8 9 10 
插入后的单链表各结点的值为：
1 2 3 4 27 5 6 7 8 9 10 
删除后的单链表各结点的值为：
1 2 3 4 27 6 7 8 9 10 
该结点的位置为：3
该单链表中无此数据元素