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

链表基础

链表分为单链表、双链表和循环链表，链表在内存中与数组不同，不是连续存储的。

C++中链表的定义方式如下：

// 单链表
struct ListNode {int val;  // 节点上存储的元素ListNode *next;  // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

这里引用代码随想录卡哥总结的数组和链表的区别：

6-203.移除链表元素

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

 

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

 

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

删除头节点和非头节点的操作是不一样的，这样会导致程序写起来较为复杂，首先给出一个使用不同操作来删除的代码：

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {while(head != NULL && head->val == val){//删除头结点ListNode* tmp =  head;//这里要临时创建一个tmp以便于后续释放空间head = head -> next;delete tmp;//释放内存}ListNode* cur = head;while(cur != NULL && cur->next!= NULL){//删除非头结点if(cur->next->val == val){ListNode* tmp = cur->next;//临时创建一个tmp以便于后续释放空间cur->next = cur->next->next;delete tmp;//释放内存}else{cur = cur->next;}}return head;}
};

删除头节点，首先判断头节点是否为空，如果为空则直接返回，当头节点指向的值为target的时候，我们删除头节点，删除前记得创建一个临时指针便于后续释放空间。

然后就可以定义一个cur来指向目前的头节点，对后续节点进行操作了。

删除后续节点，依旧判断是否为空，为空则返回，不为空且下一节点不为空时，判断指向的值是否为target，是则删除当前节点，释放空间cur向后移动一位，不是则直接向后移动一位。最后返回head即可。

使用虚拟头节点

使用虚拟头节点的好处是，当我们使用后，就可以使用统一的判断逻辑来操作后续所有节点，无需像上述代码一样需要预先判断是否为头节点。使用虚拟头节点的代码如下所示：

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyhead= new ListNode(0);dummyhead -> next = head;ListNode* cur = dummyhead;while(cur != NULL && cur->next!= NULL){//删除结点if(cur->next->val == val){ListNode* tmp = cur->next;//临时创建一个tmp以便于后续释放空间cur->next = cur->next->next;delete tmp;//释放内存}else{cur = cur->next;}}head = dummyhead->next;delete dummyhead;return head;}
};

在使用链表时，多画图可以帮助理解为什么有些地方指向next更好，有些地方则是直接指向目标。这里在最后返回时有一个需要注意的点，就是head可能已经被我们删除了，那么此时链表的头其实是dummyhead指向的下一个位置。

7-707.设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象。
• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

 

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

 

提示：

• 0 <= index, val <= 1000
• 请不要使用内置的 LinkedList 库。
• 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

设计链表问题，要求对链表有较好的掌握，第一次看还是有点晕，以前完全没学过链表这个类型，遇到了相当的困难，不过还是跟着视频写下来了。这里就只贴代码了，二刷再复习思路。

class MyLinkedList {
public:struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}};MyLinkedList() {_dummyHead = new LinkedNode(0);_size = 0;}int get(int index) {if (index > (_size - 1) || index < 0) {return -1;}LinkedNode* cur = _dummyHead->next;while(index--){ // 如果--index 就会陷入死循环cur = cur->next;}return cur->val;}void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}// 在链表最后面添加一个节点void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(cur->next != nullptr){cur = cur->next;}cur->next = newNode;_size++;}// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点// 如果index大于链表的长度，则返回空// 如果index小于0，则在头部插入节点void addAtIndex(int index, int val) {if(index > _size) return;if(index < 0) index = 0;LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(index--){cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;}void deleteAtIndex(int index) {if (index >= _size || index < 0) {return;}LinkedNode* cur = _dummyHead;while(index--){cur = cur->next;}LinkedNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;tmp = nullptr;_size--;}private:int _size;LinkedNode* _dummyHead;
};

8-206.反转链表

这题目明天来补，到时候再编辑