代码随想录算法训练营第三天 | Leetcode 203 移除链表元素 Leetcode 206 翻转链表

前言

今天的两道题目都不难，但细节需要注意。如移除链表元素用到的虚拟头节点，翻转链表的思路。翻转链表真是写了忘，忘了写，希望这次能记住。除此之外我决定每天的记录里面增加一个总结八股的部分，将来二刷再翻看文章的时候顺便也能复习八股知识点。

Leetcode 203 移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/description/

代码随想录题解：代码随想录 (programmercarl.com)

思路：不难，移除链表元素是基本功，引入虚拟头节点方便了删除节点为头节点的情况。

struct ListNode* removeElements(struct ListNode* head, int val) {
  struct ListNode *ihead;
  ihead=(struct ListNode*)malloc(sizeof(struct ListNode));
  ihead->next=head;
  struct ListNode* cur=ihead;
  while(cur->next!=NULL)
  {
    if(cur->next->val==val)
    {
       struct ListNode* del=cur->next;
       cur->next=cur->next->next;
       free(del);
    }
    else{
        cur=cur->next;
    }
  }
    head=ihead->next;
    free(ihead);
    return head;
}

Leetcode 206 翻转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/description/

代码随想录题解：代码随想录 (programmercarl.com)

思路：用代码随想录网站的一个动图就能概括了

代码：

struct ListNode* reverseList(struct ListNode* head) {
   struct ListNode *p=NULL;
   struct ListNode *q=NULL;
   while(head!=NULL)
   {
    q=head->next;
    head->next=p;
    p=head;
    head=q;
   }
   return p;
}

C++ new，delete，malloc，free 

1.实现过程

可以这么讲new封装了malloc，delete封装了free，因为new和delete实现过程中的一步就是malloc和free。new的实现机制是先调用malloc函数分配内存空间并返回一个void*的指针，第二步需要类型转换成所需类型，第三步调用对象的构造函数。delete的实现机制是先调用对象的析构函数，再调用free释放空间。

2.具体区别

new，delete是操作符，free，malloc是函数；new，delete内存分配失败时会抛出bad_alloc异常，malloc，free内存分配失败时会返回NULL；new，delete的分配空间大小自动计算，malloc，free的分配空间大小手动计算；new，delete可以重载，malloc，free不可以；new的空间大小一旦设定好就无法改变

3.new[ ]与delete[ ]

主要要谈的是删除时发生的情况。假设如果使用new[3]分配了一个指向对象的指针数组，且这个对象中有指针变量，在删除时只使用delete虽然会把这个指针数组的空间删掉，但对应的对象析构函数只调用了一次，这样剩余两个对象的析构函数没被调用，导致对象里面指针变量的空间没有正确得到释放，会导致内存泄漏，因此我们必须使用delete[]保证正确调用析构函数，释放对象中指针变量的空间。

总结

在写八股知识点总结的过程中我就发现这是一个非常正确的决定，既可以模拟面试时我需要讲出来的话，也可以帮助自己梳理知识点的逻辑，事半功倍。明天要开始学习C++的STL内容了，希望自己可以弄清底层的实现逻辑。