链表的插入删除
时间: 2023-07-11 22:19:13 浏览: 47
链表的插入和删除操作是链表中最常见的操作之一,下面分别介绍单链表的插入和删除操作。
## 单链表的插入操作
单链表的插入操作分为三种情况:
1. 在链表头插入新节点
2. 在链表尾插入新节点
3. 在链表中间插入新节点
### 在链表头插入新节点
在链表头插入新节点是最简单的情况,只需要将新节点的next指针指向原链表的头结点,然后将新节点赋值给头结点即可。
```c++
// 定义单链表结点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 在链表头插入新节点
ListNode* insertAtHead(ListNode* head, int val) {
ListNode* node = new ListNode(val);
node->next = head;
return node;
}
```
### 在链表尾插入新节点
在链表尾插入新节点需要遍历整个链表,找到链表尾部的节点,然后将新节点插入到尾部。
```c++
// 在链表尾插入新节点
ListNode* insertAtTail(ListNode* head, int val) {
ListNode* node = new ListNode(val);
if (head == nullptr) {
return node;
}
ListNode* p = head;
while (p->next != nullptr) {
p = p->next;
}
p->next = node;
return head;
}
```
### 在链表中间插入新节点
在链表中间插入新节点需要先找到插入位置的前一个节点,然后将新节点插入到指定位置。
```c++
// 在链表中间插入新节点
ListNode* insertInMiddle(ListNode* head, int pos, int val) {
ListNode* node = new ListNode(val);
if (head == nullptr) {
return node;
}
if (pos == 0) {
node->next = head;
return node;
}
ListNode* p = head;
for (int i = 0; i < pos - 1 && p != nullptr; i++) {
p = p->next;
}
if (p == nullptr) {
return head;
}
node->next = p->next;
p->next = node;
return head;
}
```
## 单链表的删除操作
单链表的删除操作也分为三种情况:
1. 删除链表头节点
2. 删除链表尾节点
3. 删除链表中间节点
### 删除链表头节点
删除链表头节点可以直接将头结点指向下一个节点即可。
```c++
// 删除链表头节点
ListNode* deleteAtHead(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
ListNode* p = head->next;
delete head;
return p;
}
```
### 删除链表尾节点
删除链表尾节点需要找到尾节点的前一个节点,将其next指针置为nullptr,然后删除尾节点。
```c++
// 删除链表尾节点
ListNode* deleteAtTail(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
if (head->next == nullptr) {
delete head;
return nullptr;
}
ListNode* p = head;
while (p->next->next != nullptr) {
p = p->next;
}
delete p->next;
p->next = nullptr;
return head;
}
```
### 删除链表中间节点
删除链表中间节点需要找到要删除节点的前一个节点和后一个节点,然后将前一个节点的next指针指向后一个节点,最后删除要删除的节点。
```c++
// 删除链表中间节点
ListNode* deleteInMiddle(ListNode* head, int pos) {
if (head == nullptr) {
return nullptr;
}
if (pos == 0) {
ListNode* p = head->next;
delete head;
return p;
}
ListNode* p = head;
for (int i = 0; i < pos - 1 && p->next != nullptr; i++) {
p = p->next;
}
if (p->next == nullptr) {
return head;
}
ListNode* q = p->next;
p->next = q->next;
delete q;
return head;
}
```