写在前面
说一下反转链表的操作, 以及在生成链表之后的析构操作, 感觉这两点其实是可以联系起来记忆的.
反转链表
一种trivial的方法当然是遍历存节点然后重新构建链表, 但是这是需要耗费$O(n)$空间的方法, 于是就有下面这种方法, 双指针记录后面未遍历的节点的方法.
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;
}
只不过这里不需要两个指针了, 因为不需要改变指向, 直接删除操作即可.