代码随想录算法训练营第二天 | 203.移除链表元素 707.设计链表 206.反转链表

代码随想录算法训练营第二天 | 203.移除链表元素 707.设计链表 206.反转链表

进入链表章节，就要和虚拟头结点（dummyhead）打交道了，还要注意边界条件和空指针异常

移除链表元素

题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

思路

对于链表的题目，很多时候使用虚拟头结点可以统一处理链表，无需考虑特殊情况（对这题来说就是要删除的节点位于头结点的情况）

具体实现方法：

• 定义虚拟头结点和cur指针（我们的操作工具）

• cur指针遍历链表，寻找并删除符合Node.val==val的头结点，这里有要注意的地方

  • 首先就是如何删除节点：cur->next = cur->next->next

    

  • 其次就是边界条件：从上图中也可以看出，我们要让cur位于cur->next->val==val的节点处才能删除节点，当检查到最后一个节点时，此时cur应该位于倒数第二个节点，所以执行完这一步后就可以停止了（执行完后cur向后走到最后一个节点）即cur->next==nullptr

  • 最后就是删除节点后cur无需后移，如果后移了，那此时后移完被cur指着的节点就没有被检查到（再强调一下，检查的是cur->next节点）

  代码

  /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode() : val(0), next(nullptr) {}
   *     ListNode(int x) : val(x), next(nullptr) {}
   *     ListNode(int x, ListNode *next) : val(x), next(next) {}
   * };
   */
  class Solution {
  public:
      ListNode* removeElements(ListNode* head, int val) {
          //使用虚拟头结点,无需分头结点是否为目标val的情况
          ListNode* dummyhead = new ListNode();
          dummyhead->next = head;
          ListNode* cur = dummyhead;
          while(cur->next!=nullptr)
          {
              if(cur->next->val==val)
              {
                  //注意最好清除一下被删除的节点，节省内存
                  ListNode* temp = cur->next;
                  cur->next = cur->next->next;
                  delete temp;
                  //无需后移，如果后移了那此时的cur->next就没有被检查
              }
              else
              {
                  //只有下一个节点不需要删除时才往后移
                  cur = cur->next;
              }
      }
      return dummyhead->next;
      }
  };
  

设计链表

题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

思路

重点依然是虚拟头结点的使用，剩下的操作都是比较基础的，直接上代码。

注意：

• 尾插的边界处理：cur也是位于要插入左边的前一位。所以尾差的while循环中是cur->next==nullptr时停止（和上面的交换是一样的，就不重复说了）

  插入操作：

  

代码

struct LinkedNode {
    int val;
    LinkedNode* next;
    LinkedNode(int val):val(val), next(nullptr){}
};

class MyLinkedList {
public:
    MyLinkedList() {
        //初始化
        _dummyhead = new LinkedNode(0);
        _size =0;
        _dummyhead->next = nullptr;
    }
    
    int get(int index) {
       	//index越界
        if(index < 0 || index >= _size) return -1;
        LinkedNode* curr = _dummyhead->next;
       	//cur寻找index对应的节点
        for(int i = 0; i < index; ++i){
            curr = curr->next;
        }
        return curr->val;
    }
    
    void addAtHead(int val) {
        //头插法
        LinkedNode* newnode = new LinkedNode(val);
        LinkedNode* curr = _dummyhead->next;
        _dummyhead->next = newnode;
        newnode->next = curr;
        _size++;
        return;
    }
    
    void addAtTail(int val) {
        //尾插法
        LinkedNode* newnode = new LinkedNode(val);
        LinkedNode* curr = _dummyhead;
        //到达尾部
        while (curr->next != nullptr) {
            curr = curr->next;
        }
        curr->next = newnode;
        newnode->next = nullptr;
        _size++;
        return;
    }
    
    void addAtIndex(int index, int val) {
        if(index < 0) return;
        if(index > _size) return;
        LinkedNode* newnode = new LinkedNode(val);
        //到达index处的前一个节点
        LinkedNode* curr = _dummyhead;
        for(int i = 0; i < index; ++i){
            curr = curr->next;
        }
        //插入新节点
        newnode->next = curr->next;
        curr->next = newnode;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index >= _size) return;
        LinkedNode* curr = _dummyhead;
        for(int i = 0; i < index; ++i)
        {
            curr = curr->next;
        }
        LinkedNode* temp = curr->next;
        curr->next = curr->next->next;
        _size--;
        delete temp;
    }

private:
    LinkedNode* _dummyhead;
    int _size;

};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

反转链表

题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

思路

这道题就没必要使用虚拟头节点了（硬要用也没问题）

1. 双指针法

   • pre,cur两个指针指向改变箭头指向的节点（下面的图片很清晰），注意cur遍历链表的结束条件是cur==nullptr，因为最后一个节点也需要翻转箭头，进行完这步后，cur就指向null了

     

2. 递归法

   • 递归法和双指针法其实本质是一样的，递归需要解决的就是递归结束条件（和上面一样）和转移表达式（cur = temp, pre = cur），只是和双指针的写法不一样而已

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    ListNode* reverse(ListNode* cur,ListNode* pre)
    {
        //终止条件
        if(cur==nullptr) return pre;
        
        ListNode* temp = cur->next;
        cur->next = pre;
        
        return reverse(temp,cur);  
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        //这是双指针实现
        // while(cur!=nullptr)
        // {
        //     ListNode* temp = cur->next;
        //     cur->next = pre;
        //     pre = cur;
        //     cur = temp;
        // }
        // return pre;

        //递归实现
        return reverse(cur,pre);
    }
};

总结：

链表的题目中重要的就是虚拟头结点，边界条件处理（可以自己假设如果只有一个头结点的情况来判断自己的边界情况对不对），执行各种操作（交换，插入……）时temp的临保存，next的不同顺序调用。