算法训练营第三天 | 203.移除链表元素、707.设计链表 、206.反转链表

关于链表我们应该了解什么：

---

问题（ 一 ）

题目描述 ：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

题目链接：

203. 移除链表元素 - 力扣（LeetCode）

---

问题分析：

          这到题目算是链表的基础操作 ， 我这里写的是链表的前面是一个虚拟头节点，这样我们就不用考虑删除元素是否是头节点这个情况了 。主要掌握虚拟头节点，当然可以不用这个方法，但是这样会时链表的操作变得更加简洁。  删除的核心操作就是，找到要删除节点的前一个节点：他的next 就是我们要删除的节点    如果删除的节点的前一个节点是p,   那么 p->next = p->next->next。

视频讲解：

手把手带你学会操作链表 | LeetCode：203.移除链表元素_哔哩哔哩_bilibili

---

解决方案：

 ListNode* removeElements(ListNode* head, int val) {
     ListNode *virtualNode =new ListNode;    //定义一个虚拟头结点
     virtualNode->next=head;
     ListNode *temp=virtualNode;
     //遍历链表
     while( temp!= NULL && temp->next!=NULL){
        if(temp->next->val==val){   //找到了满足条件的节点
           //删除节点
           head=temp->next;
           temp->next=temp->next->next;
           delete head;
           continue;
         }
          temp=temp->next;
      }
     return virtualNode->next;
    }

问题（ 二  ）

题目描述 ：

设计链表，可以是单链表也可以是双链表。

题目链接：

707. 设计链表 - 力扣（LeetCode）

问题分析：

        我自己给出的答案是单链表的设计 ， 包括一些基础操作，增删查。我们需要知道的是链表也是从0开始计数的，删除和在指定位置插入，我们都是找到待操作位置的前一个位置。

视频讲解：

帮你把链表操作学个通透！LeetCode：707.设计链表_哔哩哔哩_bilibili

解决方案：

class MyLinkedList {    //才用虚拟头节点法
 
public:
    MyLinkedList() {
        head = new ListHead;
        head->next = NULL;
        head->val = 0;
        size = 0;
    }
 
    //获取元素
    int get(int index) {
        //防御性编程
        if (!head ) return -1;    //链表不存在,或者为空
        if (head->next == NULL)  return -1;
        if (index < 0)   return -1;  //下标不合法  
        if (index >= size)  return -1;
        int i = 0;
        ListNode* p = head;  //指向虚拟头结点
        while (i <=index) {
            p = p->next;
            i++;
        }
        return p->val;
    }
 
    //头部添加
    void addAtHead(int val) {
        if (!head) return;
        ListNode* node = new ListNode;    //生成一个节点
        node->val = val;
        node->next = head->next;
        head->next = node;
        size++;
    }
 
    //尾部添加
    void addAtTail(int val) {
        if (!head) return;    //判断链表是否存在
        ListNode* node = new ListNode;    //生成一个节点
        node->val = val;
        ListNode* p = head;   //指向第一个节点
        while (p->next!=NULL) {
            p = p->next;
        }
        //循环结束后说明刚好处于最后一个位置
        node->next = p->next;
        p->next = node;
        size++;
    }
 
    //在指定位置添加
    void addAtIndex(int index, int val) {
        if (!head) return;   //链表不存在
        if (index < 0) return; //位置不合法
        if (index > size) return;
        ListNode* p = head;   //指向虚拟头结点
        while ( index--) {
            p = p->next;
        }
        ListNode* node = new ListNode;    //生成一个节点
        node->val = val;
        node->next = p->next;
        p->next = node;
        size++;
    }
 
    //删除位置的元素
    void deleteAtIndex(int index) {
        if (!head ) return;
        if (head->next == NULL)  return;   //没有元素
        if (index < 0)   return ;  //下标不合法  
        if (index >= size)  return ;
        LinkList* p = head;
        if (index == 0) {
            head->next = head->next->next;
            size--;
            return;
        }
 
        while ( index-- ) {
            p = p->next;
        }
        cout << p->val << endl;
        LinkList* temp = p->next;
        p->next = p->next->next;
        delete temp;
        size--;
    }
    void print() {
        ListNode* node = head->next;
        while (node) {
            cout << node->val << "  ";
            node = node->next;
        }
        cout << endl;
    }
 
private:
  //节点结构
typedef struct LinkList {
    struct LinkList* next;
    int val;
}ListHead,ListNode;
    ListHead* head;
    int size;   //链表的长度
  
};

问题（  三  ） 

题目描述 ：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

题目链接：

206. 反转链表 - 力扣（LeetCode）

问题分析：

        这到题目，我们采用双指针的思路。指针 pro 用来记录我们head的前一个节点，开始没有翻转之前，head的前一个节点为NULL ，所有pro初始值为NULL，而我们的第二个指针 temp 则用来记录head的下一个节点。

 循环遍历我们的链表，终止条件是  head 指针为空，1-》2断开之后，1-》的next指向了 NULL，然后我们的  temp继续往后移动，而我们的 pro 则指向 head。

视频加文字讲解：

 解决方案：

ListNode* reverseList(ListNode* head) {
    if(!head)  return NULL;   //链表为空
    if(head->next==NULL) return head;    //只有一个元素的情况
    ListNode *pro=NULL ; //用来只想当前位置的前一个节点
    ListNode *temp=head ;
    while( head ){
       temp = temp->next;
       head->next=pro;
 
       pro=head;
       head=temp;
    }
    head=pro;
    return head;  
}