在单链表最后一个元素后插入新元素c++代码
时间: 2024-05-10 16:17:35 浏览: 7
假设单链表的结点定义为:
```c++
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
```
则在单链表最后一个元素后插入新元素的代码可以如下实现:
```c++
void insertAtTail(ListNode* head, int val) {
ListNode* newNode = new ListNode(val);
if (head == NULL) {
head = newNode;
return;
}
ListNode* cur = head;
while (cur->next != NULL) {
cur = cur->next;
}
cur->next = newNode;
}
```
这里的思路是,先创建一个新节点,然后遍历链表找到最后一个节点,将最后一个节点的 next 指针指向新节点即可。需要注意的是,如果链表为空,则直接将新节点作为头结点。
相关问题
单链表在最后一个元素后插入一个元素的时间复杂度
单链表在最后一个元素后插入一个元素的时间复杂度取决于是否维护了一个指向尾节点的指针。
如果维护了一个指向尾节点的指针,则在最后一个元素后插入一个元素的时间复杂度为O(1),即常数时间。这是因为我们可以直接访问尾节点并将新元素插入到尾节点的“next”指针处。
如果没有维护一个指向尾节点的指针,则需要遍历整个链表来找到最后一个元素,然后在最后一个元素后插入新元素。因此,时间复杂度将是O(n),其中n是链表中的元素数量。
因此,如果需要频繁在链表的末尾插入元素,建议维护一个指向尾节点的指针,以获得O(1)的时间复杂度。
在带头结点的单链表表尾处插入一个新元素代码
假设我们已经定义了单链表的结构体和节点结构体,其中头结点为`head`。以下是在带头结点的单链表表尾处插入一个新元素的代码:
```c
// 定义节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 定义单链表结构体
typedef struct LinkedList {
Node* head;
} LinkedList;
// 在表尾插入新元素
void insertAtTail(LinkedList* list, int data) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
newNode->data = data; // 设置新节点的值
newNode->next = NULL; // 新节点的 next 指针指向 NULL
Node* current = list->head;
while (current->next != NULL) { // 找到链表的最后一个节点
current = current->next;
}
current->next = newNode; // 将新节点插入到链表的尾部
}
```
该函数首先创建一个新节点,然后遍历链表,找到链表的最后一个节点,最后将新节点插入到链表的尾部。