反转链表与链表的析构操作(C++)

阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6



tags: C++ DSA

写在前面

说一下反转链表的操作, 以及在生成链表之后的析构操作, 感觉这两点其实是可以联系起来记忆的.

反转链表

​206. 反转链表 - 力扣(LeetCode)​​;

一种trivial的方法当然是遍历存节点然后重新构建链表, 但是这是需要耗费反转链表与链表的析构操作(C++)_反转链表空间的方法, 于是就有下面这种方法, 双指针记录后面未遍历的节点的方法.

class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur=head, *pre=nullptr;
while (cur) {
auto tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
};

注意一下cur更新的方法, 不是传统的​​cur=cur->next;​​了, 而是直接通过前面记录的未遍历过节点来完成.

链表的析构

回想一下析构的过程, 应该是构造的逆操作, 就是说, 先删除头结点, 删除之前保存剩余节点的信息, 然后依次完成此过程. 是不是跟反转链表很像?

LinkedList::~LinkedList() {
ListNode* cur;
while (head->next) {
cur = head->next;
delete head;
head = cur;
}
delete head;
}

只不过这里不需要两个指针了, 因为不需要改变指向, 直接删除操作即可.


阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6
标签: c++