C++实现向链表尾部插入数据val的代码
时间: 2024-09-28 08:06:51 浏览: 20
在C++中,向单向链表的尾部插入数据通常涉及创建一个新的节点,并将其链接到当前列表的最后一个元素之后。下面是一个简单的示例,假设我们有一个`Node`结构体表示链表的节点:
```cpp
// 定义链表节点
struct Node {
int val;
Node* next; // 指向下一个节点的指针
Node(int v) : val(v), next(nullptr) {} // 构造函数
};
// 向链表尾部插入新值的函数
void insertAtTail(Node*& head, int val) {
if (head == nullptr) { // 如果链表为空
head = new Node(val); // 创建新的头节点并赋值
} else {
Node* current = head; // 从头开始遍历
while (current->next != nullptr) { // 找到最后一个非空节点
current = current->next;
}
current->next = new Node(val); // 将新节点链接到尾部
}
}
```
在这个例子中,`insertAtTail`函数接受链表的头节点引用`head`和新值`val`作为参数。如果链表为空,它会直接将新值作为头节点创建;否则,它会遍历链表直到找到尾部,然后在那里插入新节点。
相关问题
c++实现链表的插入
链表的插入操作可以分为两种情况:
第一种情况,插入到链表的头部:
```c++
#include <iostream>
using namespace std;
// 链表节点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 插入节点到链表的头部
ListNode* insertNodeAtHead(ListNode* head, int val) {
ListNode* newNode = new ListNode(val);
newNode->next = head;
return newNode;
}
int main() {
ListNode* head = NULL;
head = insertNodeAtHead(head, 3);
head = insertNodeAtHead(head, 2);
head = insertNodeAtHead(head, 1);
// 输出链表
ListNode* p = head;
while (p != NULL) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
return 0;
}
```
第二种情况,插入到链表的中间或尾部:
```c++
#include <iostream>
using namespace std;
// 链表节点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 插入节点到链表的中间或尾部
ListNode* insertNode(ListNode* head, int val, int pos) {
ListNode* newNode = new ListNode(val);
if (pos == 1) {
newNode->next = head;
return newNode;
}
ListNode* p = head;
int i = 1;
while (p != NULL && i < pos - 1) {
p = p->next;
i++;
}
if (p == NULL) {
return head;
}
newNode->next = p->next;
p->next = newNode;
return head;
}
int main() {
ListNode* head = NULL;
head = insertNode(head, 1, 1);
head = insertNode(head, 3, 2);
head = insertNode(head, 2, 2);
head = insertNode(head, 5, 4);
head = insertNode(head, 4, 4);
// 输出链表
ListNode* p = head;
while (p != NULL) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
return 0;
}
```
c++实现有序链表的合并
假设有两个有序链表A和B,现在要将它们合并成一个有序链表C。可以按照以下步骤实现:
1. 定义一个新的链表C,并初始化为空。
2. 定义三个指针pA、pB、pC,分别指向链表A、B、C的头节点。
3. 比较pA和pB所指向节点的值,将较小的节点插入到链表C的尾部,并将pC指向新插入的节点。
4. 移动指针pA或pB到下一个节点,再重复步骤3,直到其中一个链表遍历完毕。
5. 将另一个链表剩余的节点插入到链表C的尾部。
以下是具体的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode *pA = l1, *pB = l2, *pC = NULL, *tail = NULL;
struct ListNode *head = (struct ListNode*) malloc(sizeof(struct ListNode));
head->next = NULL;
pC = tail = head;
while (pA && pB) {
if (pA->val <= pB->val) {
tail->next = pA;
tail = pA;
pA = pA->next;
} else {
tail->next = pB;
tail = pB;
pB = pB->next;
}
}
if (pA) {
tail->next = pA;
} else {
tail->next = pB;
}
pC = head->next;
free(head);
return pC;
}
```
该函数的时间复杂度为O(m+n),其中m和n分别为两个链表的长度。