在单链表的某个节点之前或节点之后插入一个新节点。或者在单链表的尾部插入一个节点或单链表的头部插入一个节点。
时间: 2024-03-20 21:41:28 浏览: 120
好的,针对您的问题,我可以给您提供以下的代码示例,以C++语言为例:
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* insertBefore(ListNode* head, int insertVal) {
ListNode* node = new ListNode(insertVal);
if(!head) {
node->next = node;
return node;
}
ListNode* cur = head;
while(cur->next != head && (cur->next->val < insertVal || cur->val >= insertVal)) {
cur = cur->next;
}
node->next = cur->next;
cur->next = node;
return head;
}
ListNode* insertAfter(ListNode* head, int insertVal) {
ListNode* node = new ListNode(insertVal);
if(!head) {
node->next = node;
return node;
}
ListNode* cur = head;
while(cur->next != head && (cur->next->val <= insertVal || cur->val > insertVal)) {
cur = cur->next;
}
node->next = cur->next;
cur->next = node;
if(insertVal < head->val) {
return node;
}
return head;
}
ListNode* insertAtTail(ListNode* head, int insertVal) {
ListNode* node = new ListNode(insertVal);
if(!head) {
node->next = node;
return node;
}
ListNode* cur = head;
while(cur->next != head) {
cur = cur->next;
}
node->next = cur->next;
cur->next = node;
return head;
}
ListNode* insertAtHead(ListNode* head, int insertVal) {
ListNode* node = new ListNode(insertVal);
if(!head) {
node->next = node;
return node;
}
ListNode* cur = head;
while(cur->next != head) {
cur = cur->next;
}
node->next = head;
cur->next = node;
return node;
}
int main() {
ListNode* head = new ListNode(1);
head->next = head;
head = insertBefore(head, 3);
head = insertBefore(head, 2);
head = insertAfter(head, 4);
head = insertAfter(head, 5);
head = insertAtTail(head, 6);
head = insertAtHead(head, 0);
ListNode* cur = head;
do {
cout << cur->val << " ";
cur = cur->next;
} while(cur != head);
cout << endl;
return 0;
}
```
上述示例包括四个函数:insertBefore、insertAfter、insertAtTail和insertAtHead,分别用于在单链表的某个节点之前、之后、尾部和头部插入新节点。
其中,每个节点由一个整数值和指向下一个节点的指针组成。当单链表为空时,头指针指向空指针。
在插入节点时,我们需要遍历单链表,找到插入位置。具体而言,对于插入到某节点之前或之后,我们需要找到前一个节点,然后将新节点插入到前一个节点的next指针指向的位置;对于插入到尾部或头部,我们需要找到单链表的尾节点,然后在尾节点的next指针指向的位置插入新节点。
希望这个回答能对您有所帮助!
阅读全文