链表基础
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链表的数据域没什么好说的，关在在于指针的玩法，根据指针的指向与数量可将链表分为如下类型：
-
单链表：刚刚说的就是单链表。
-
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点；既可以向前查询也可以向后查询。
- 循环链表:循环链表，顾名思义，就是链表首尾相连;可以用来解决约瑟夫环问题。
链表存储方式
数组是在内存中是连续分布的，但是链表在内存中不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
链表操作
删除节点
C/C++使用delete回收内存，防止内存泄漏
添加节点
性能对比
203. 移除链表元素
题目链接：203. 移除链表元素
文档讲解：代码随想录
状态：普通方法AC，了解递归（难啊）
思路
涉及增加/删除操作时，最好规定一个虚拟头节点dummy_head,更加方便
本题普通思路根据链表性质即可，else cur = cur->next;注意什么时候cur后移。
递归感觉很烧脑，记住三板斧：函数做什么（输入、返回）、终止条件、拆分小问题、
题解
class Solution {
public:
ListNode* removeElements(ListNode* head, int val)
{//最清晰正确的方法
// ListNode *dummy_head = new ListNode(0,head);
// ListNode *cur = dummy_head;
// while(cur->next!=nullptr)
// {
// if(cur->next->val == val)
// {
// ListNode* temp = cur->next; // 保存要删除的节点
// cur->next = cur->next->next; // 跳过要删除的节点
// delete temp; // 删除保存的节点
// }
// else cur = cur->next;//出错
// }
// ListNode *result = dummy_head->next;
// delete dummy_head;
// return result;
//递归方法，注意递归的思考方式
if(head == nullptr) return nullptr;
else
{
if(head->val == val)
{
ListNode* newHead = removeElements(head->next, val);
delete head;//注意删除细节
return newHead;
}
else
{
//关键点
head->next = removeElements(head->next,val);
return head;
}
}
}
};
707.设计链表
思路
双链表待补充
注意MyLinkedList是一个链表类，一个对象代表一串struct（自己定义的ListNode），注意数据结构的关系
算法方面没有任何问题，主要注意是否使用虚拟头节点、善于使用size维护链表，而不是根据指针判断。
题解
class MyLinkedList {
public:
//链表节点定义
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(nullptr){}
};
//该类是一个链表
MyLinkedList() {
dummy_head = new ListNode(0);
size = 0;
}
int get(int index) {
ListNode *cur = dummy_head;
if(index<0||index>(size-1))return -1;
while(index--)
{
cur = cur->next;
}
return cur->next->val;
}
void addAtHead(int val) {
if(size == 0){dummy_head->next = new ListNode(val);size++;}
else
{
ListNode *temp = dummy_head->next;
dummy_head->next = new ListNode(val);
dummy_head->next->next = temp;
size++;
}
}
void addAtTail(int val) {
ListNode *cur = dummy_head;
if(size == 0){dummy_head->next = new ListNode(val);size++;}
else
{
while(cur->next!=nullptr)
{
cur = cur->next;
}
cur->next = new ListNode(val);
size++;
}
}
void addAtIndex(int index, int val) {
ListNode *cur = dummy_head;
if(index == size)addAtTail(val);
else if(index > size||index<0)return;
else
{
while(index--)
{
cur = cur->next;
}
ListNode *temp = new ListNode(val);
temp->next = cur->next;
cur->next = temp;
size++;
}
}
void deleteAtIndex(int index) {
ListNode *cur = dummy_head;
if(index<0||index>=size)return;
else
{
while(index--)
{
cur = cur->next;
}
ListNode *temp = cur->next;
cur->next = cur->next->next;
delete temp;
temp = nullptr;
size --;
}
}
private:
//长度定义
int size;
ListNode *dummy_head;
};
206.反转链表
思路
简单模拟一下过程，发现单指针不能往回指，要双指操作，关键思考为什么Pre开始为Null
递归太神奇，三板斧理解再理解
补充：终止条件考虑循环极端情况也要考虑输入极端情况！！！，不建议使用
题解
// /**
// * 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 *pre,ListNode *cur)
// // {
// // if(cur == nullptr)return pre;
// // ListNode *temp = cur->next;
// // cur->next = pre;
// // return reverse(cur,temp);
// // }
// ListNode* reverseList(ListNode* head) {
// // 常规指针法
// // ListNode *cur = head;
// // ListNode *pre = nullptr;
// // while(cur != nullptr)
// // {
// // ListNode *temp = cur->next;
// // cur->next = pre;
// // pre = cur;
// // cur = temp;
// // }
// // return pre;
// // 递归法混乱啊
// // ListNode *cur = head;
// // ListNode *pre = nullptr;
// // return reverse(pre,cur);
// //递归法二
// if(head->next == nullptr||head == nullptr)return head;
// //拆解问题
// ListNode *temp = head->next;
// head->next = nullptr;
// return reverseList(temp)->next = head;
// }
// };
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) {//空链表也要纳入最终条件
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};