本文没啥干货,纯属笔记,建议出门左拐哈
目录
1、创建单向链表
2、在链表结尾添加元素
3、从链表中删除第一个值为 val 的元素
4、测试用例
1、创建单向链表
单向链表可以使用结构体的形式创建,定义一个名为 ListNode 的结构体如下:
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {} // 重载函数,默认值为1
ListNode(int x) : val(x), next(nullptr) {} // 重载函数,按值 x 初始化
ListNode(int x, ListNode *next) : val(x), next(next) {} // 重载函数,使用新的节点初始化
};
该结构体定义过程中使用到了函数重载。
函数重载:
同一作用域内的几个名字相同但形参列表不同的函数称作重载(overloaded)函数 。当调用这些操作时,编译器会根据传递的实参的类型推断想要的是那个函数。
2、在链表结尾添加元素
链表结尾添加元素的方式有很多种
1、首先是最复杂的一种:使用双重指针
void AddToTail_0(ListNode** head, int val)
{
ListNode* pNew = new ListNode(val); // 初始化要加入的尾节点
if(*head == nullptr) // 首先判断头指针
{
*head = pNew;
}
else // 头指针不为空则继续后续的判断
{
ListNode *p = *head;
while(p->next != nullptr) // 寻找结尾
p = p->next;
p->next = pNew;
}
}
2、简单的:使用单重指针
void AddToTail(ListNode* head, int val)
{
ListNode* pNew = new ListNode(val);
if(head == nullptr)
head = pNew;
else
{
ListNode* node = head;
while(node->next != nullptr)
node = node->next;
node->next = pNew;
}
}
这种方式第一步与双重指针类似,必须要先判断头节点本身是否为空。如果嫌这样还是麻烦的话还有一种简化的方式:使用哨兵节点。哨兵节点作为临时节点插入到头节点之前,这样就可以从开始就使用 p->next 的格式判断了,但是这种情况记住最后要释放哨兵节点。代码如下:
void AddToTail(ListNode* head, int val)
{
ListNode* prev = new ListNode(0); // 定义哨兵节点
prev->next = head; // 将哨兵节点放到头节点前
ListNode* pNew = new ListNode(val); // 初始化要加入的尾节点
ListNode* node = prev;
while(node->next != nullptr)
node = node->next;
node->next = pNew;
head = prev->next; // 从哨兵节点后取回头节点
delete prev; // 释放哨兵节点的内存
}
3、从链表中删除第一个值为 val 的元素
直接放单指针的版本了,双指针容易绕晕就不记了。
void delNode(ListNode* head, int val)
{
ListNode* pToBrDel = nullptr; // 暂存被删除节点,用于释放其占用的内存
if(head == nullptr) // 链表为空
return ;
else if(head->val == val) // 第一个就是要找的值
{
pToBrDel = head;
head = head->next;
}
ListNode* node = head; // 定义临时节点
while(node->next != nullptr)
{
if(node->next->val == val)
{
pToBrDel = node->next;
node->next = node->next->next;
break;
}
node = node->next;
}
if(pToBrDel != nullptr) // 释放被删除节点所占的内存
delete pToBrDel;
}
使用哨兵节点的版本:
void delNode(ListNode* head, int val)
{
ListNode* pToBrDel = nullptr; // 暂存被删除节点,用于释放其占用的内存
ListNode* prev = new ListNode(0); // 定义哨兵节点
prev->next = head;
ListNode* node = prev; // 定义临时节点
while(node->next != nullptr)
{
if(node->next->val == val)
{
pToBrDel = node->next;
node->next = node->next->next;
break;
}
node = node->next;
}
if(pToBrDel != nullptr) // 释放被删除节点所占的内存
delete pToBrDel;
head = prev->next; // 从哨兵节点后取回头节点
delete prev; // 释放哨兵节点的内存
}
4、测试用例
int main()
{
ListNode *li = new ListNode(); // 初始化链表
cout << "insert operator: " << endl;
AddToTail(li, 1);
AddToTail(li, 2);
AddToTail(li, 3);
ListNode *temp = li;
while(1) // 打印
if(temp != nullptr)
{
cout << temp->val << endl;
temp = temp->next;
}
else break;
cout << "delete operator: " << endl;
delNode(li, 2);
delNode(li, 1);
ListNode *temp1 = li;
while(1) // 打印
if(temp1 != nullptr)
{
cout << temp1->val << endl;
temp1 = temp1->next;
}
else break;
return 0;
}
/**************** 运行结果
0
1
2
3
delete operator:
0
3
****************/
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)