代码随想录算法训练营Day03 | 链表理论基础、203.移除链表元素 、707.设计链表、206.反转链表

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

链表理论基础

• C/C++的定义链表节点方式：

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

• 数组与链表的对比：

203.移除链表元素

• 题目链接：203. 移除链表元素 - 力扣（LeetCode）
• 讲解链接：代码随想录 (programmercarl.com)
• 状态：提交一次后AC。

思路与重点

• 使用了一个虚拟头节点，指向题目给出的头节点，然后遍历链表开始删除，最后返回虚拟头节点的next指针即可。主要使用C++时不要忘记释放掉被删除节点占用的空间！

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummy_head = new ListNode(-1, head);ListNode* cur = dummy_head;while(cur->next != nullptr){if(cur->next->val == val){ListNode* temp = cur->next->next;delete cur->next;cur->next = temp;}else cur = cur->next;}head = dummy_head->next;delete dummy_head;return head;}
};

• 链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点，可以用递归实现。

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 基础情况：空链表if (head == nullptr) {return nullptr;}// 递归处理if (head->val == val) {ListNode* newHead = removeElements(head->next, val);delete head;return newHead;} else {head->next = removeElements(head->next, val);return head;}}
};

707.设计链表

• 题目链接：707. 设计链表 - 力扣（LeetCode）
• 讲解链接：代码随想录 (programmercarl.com)
• 状态：直接看题解了。

思路与重点

• 使用虚拟头结点可以很大降低写代码的复杂程度。
• 注意LinkedNode* cur = _dummyHead;和LinkedNode* cur = _dummyHead->next;

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 < 0 || index >= _size){return -1;}LinkedNode* cur = _dummyHead->next;while(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) cur = cur->next;cur->next = newNode;_size++;        }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 >= 0 && index < _size){LinkedNode* cur = _dummyHead;while(index--){cur = cur->next;}LinkedNode* temp = cur->next;cur->next = cur->next->next;delete temp;temp = nullptr;_size--;}  else return;}private:LinkedNode* _dummyHead;int _size;
};

206.反转链表

• 题目链接：206. 反转链表 - 力扣（LeetCode）
• 讲解链接：代码随想录 (programmercarl.com)
• 状态：直接去看卡哥视频了。

思路与重点

• 用双指针法很好解决，不需要用新的链表分配空间。卡哥的视频讲的是真清晰啊，用以下的动图很好理解。

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur = head;ListNode* pre = nullptr;ListNode* temp = nullptr;while(cur){temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}
};

• 也可以用递归的方式解决，递归的解决思路其实和双指针法一样。

class Solution {
public:ListNode* reverseList(ListNode* head) {return reverse(nullptr, head);}ListNode* reverse(ListNode* pre, ListNode* cur){if(!cur) return pre;ListNode* temp = cur->next;cur->next = pre;return reverse(cur, temp);}
};