LeetCode 203 移除元素

题目链接

链表移除元素时用什么方法更好？为什么？

?方法：虚拟头结点
? 使用虚拟头结点的原因

? ? 众所周知，单链表里除了头结点，其他结点都是可以被前一个指向它的结点找到的。所以除了头结点以外，单链表里的其他结点进行删除操作比较方便。在没有虚拟头结点的情况下，还要专门写一部分代码考虑清理头结点的情况。

? ? ?所以，虚拟头结点的思想就派上用场了。虚拟头结点指向头结点，它让头结点也可以被前一个结点找到，这样的话，处理头结点就跟处理其他结点一样了，不用另写代码专门考虑头结点的情况。

自己出现过问题，要提醒自己的地方：

? ?在代码中，定义指针cur的目的是为了遍历链表的。

? 我在定义ListNode *cur =xu; 的时候犯了难，我以为它是链表里的一个结点，可它怎么起到指针的作用呢？所以一头雾水的。

后来我搞清楚了，也明白了。

**ListNode * abc = new ListNode(); 这样才是创建一个结点；**

**ListNode * def ; 这是一个用于ListNode的指针。**
?

代码实现

 //定义一个虚拟头结点 xu
 ListNode * xu = new ListNode();
 xu->next =head;

 //定义一个遍历用的指针cur,初始时指向虚拟头结点
 ListNode *cur = xu;

 //开始遍历
  while(cur->next != NULL) {
     if(cur->next->val != val) {cur = cur->next;}
     else{
          //此时，cur所指结点的下一个就是待删除结点
          //暂时保护待删除结点
          ListNode * tmp = cur->next;
          cur->next = cur->next->next;
          delete tmp; //C++里需要自己清除内存
          }
      }
          
//删完了，返回head
 head = xu->next; //这是考虑头结点被删了的情况，如果没被删,head就是等于xu->next。删了就要更新了
 delete xu;//虚拟头结点要删了，清内存
 return head;

时间复杂度：O(n)

空间复杂度：O(n)?

?文章链接

视频链接

LeetCode 206 反转链表

题目链接

做题思想：双指针的思路。cur往后遍历，pre跟上。

? ?使用双指针思路，定义两个指针，pre和cur，是让cur先走的。所以cur初始化指向head；pre初始化指向为NULL。

为什么pre初始化指向为NULL？因为反转链表后，反转前的第一个结点在反转后是尾结点，尾结点要指向空，所以pre要初始化为NULL；

定义一个中间指针tmp，用于在循环中，暂时保护原方向的cur->next,因为要反转，所以要改变方向，所以要把原方向的cur->next保护起来。

使用cur作为while的条件。为什么呢？?因为cur先走，所以当cur走到为NULL时，说明翻转完了，此时退出循环。而cur走到为NULL时，pre指向的，就是新方向的头结点。

在循环中，先把原方向下的cur->next用tmp保护起来。然后修改cur->next 为pre，修改方向。然后更新pre与cur。把cur赋给pre就更新了pre；把tmp保存的原方向下的cur->next,赋给了cur ，这样就更新了cur。

?while循环结束，退出。返回新方向下的头结点。

代码:

 //使用双指针的思路，定义两个指针 pre，cur，cur先走
    ListNode * cur = head;
    ListNode *pre = NULL;
//定义一个指针tmp，暂时保存cur->next指向的结点
    ListNode * tmp ;
    while(cur) {
         //保存cur->next正常方向指向的结点
         tmp = cur->next;
         //换方向,cur所指的点，方向指向pre
         cur->next = pre;
         //更新
         pre = cur;
         cur =tmp;
           }//cur为空，循环结束时，换好了。此时的头结点是pre
 
    delete tmp;
    return pre;

时间复杂度：O(n)

? ? ? 操作的是整个链表，链表长度为n。循环执行n次，循环里的语句4条；初始化语句3条，结尾部分2条；f(n) = 4n +5? 化简就是O(n)

空间复杂度:O(n)

? ??操作的是整个链表，链表长度为n

文章链接

视频链接

707设计链表

题目链接

题目中已说明n从0开始，所以index为0,代表头结点。

设计链表，需要写5个函数，但其中的重点是什么？

? 重点是：怎么找到第n个点？

? ? ?（1）找第n个点，令cur指向头结点，头结点代表的所有是0,（题中已得知此前提）

? ? 当while(index--){cur=cur->next;} index减为0，退出循环时，cur指向的就是第n个点。

? （2）当涉及在第n个位置的插入或删除时，要找的是第n个位置的前一个点，也就是第n-1个点，令cur指向虚拟头结点，当while(index--){cur=cur->next;}? ，index减为0的时候，退出while循环。cur指向的就是第n-1个点。

代码实现：

class MyLinkedList {
public:
 //自己定义链表的结构
    struct LinkedNode{
         int val;
         LinkedNode *next;
         LinkedNode(int val):val(val), next(nullptr){}
     };
    MyLinkedList() {
      //new一个虚拟头结点
      dummyHead  = new LinkedNode(0);
      size = 0;
     
    }
    
    int get(int index) {
        //获取第index个结点的值
        //剔除索引无效的情况
      if(index > (size-1) || index < 0) {return -1; }
       LinkedNode *cur = dummyHead->next;
        //假设要的是第0个结点，也就是头结点
        while(index--) {cur = cur->next;}
        return cur->val;

    }
    

    void addAtHead(int val) {
        //头部加一个结点
        //新建一个结点，并赋值
        LinkedNode *newhead = new LinkedNode(val);
        newhead->next = dummyHead->next;
        dummyHead->next = newhead;
        size++;

    }
    
    void addAtTail(int val) {
        //尾巴加一个新结点
        LinkedNode *newtail = new LinkedNode(val);
        newtail->next = NULL;
        LinkedNode *cur = dummyHead;
        //让cur去遍历，cur->next为空时，cur来到最尾结点
        while(cur->next){cur = cur->next;}
        cur->next = newtail;
        size++;
    }
    
    void addAtIndex(int index, int val) {
    //在链表中的第 index 个节点之前添加值为 val的节点
    //要在第index个结点前面插入一个，新插入的点就是第index个，所以我们应该先知道index-1的，让cur指向index-1的，cur->next就是原先第index个的。
      if(index > size) {return ;}
      LinkedNode *cur = dummyHead;//让cur最开始指向虚拟头结点，考虑插入第0个点前面插入

     
     //new一个结点,并赋值为val
        LinkedNode *newNode = new LinkedNode(val);
        
    //cur最开始指向虚拟头结点，cur->next指向头结点。假设插入在头结点之前
     while(index--) {cur=cur->next;}
        
        //插入
        newNode->next = cur->next; //此时的cur->next指向原先第index个
        cur->next = newNode;
        size++;

    }
    
    void deleteAtIndex(int index) {
    //删除第index个结点的值
    //让cur从虚拟头结点出发，index减为0时，cur就指向第index-1个。

     //剔除索引无效的情况
    if(index <0 || index >= size) return; 
    
    LinkedNode *cur = dummyHead;
    //cur最开始指向虚拟头结点，cur->next指向头结点。假设删除头结点之前
     while(index--) {cur=cur->next;}//循环出来时，cur指向待删除结点的前一个结点;

    //删除
     LinkedNode *tmp = cur->next;
     cur->next = cur->next->next;
     delete tmp;
     size--;
    }

    private:
    int size;
    LinkedNode* dummyHead;    

};

个人总结：

在这些第n个位置的插入/删除操作，重要的是找到目标结点的前一个结点。用cur指向它。

个人存在的一点疑问：在正常的代码里，虚拟头结点的话，是要指向头结点的。可是力扣这题里并没有给出头结点head，那怎么让dummyHead指向链表的头结点呢？（在5个设计函数里，是默认dummyHead指向头结点的。）

个人遇到不懂的地方：C++，这里的类。

文章链接

视频链接