1.题目要求
LeetCode203移除链表指定元素
LeetCode707设计链表
LeetCode206反转链表
这三个题目包含了链表的初始化、插入头尾结点、插入删除第n个结点，删除指定内容的结点、链表的逆置等，下面我将一一讲解并展示源代码。
2.具体操作
2.1LeetCode中链表的初始化
我下面所讲述的是带有虚拟头结点的初始化：
首先在链表类里面定义一个链表结点的结构体，该结构体的主要内容包括val（该结点的值）、next（该结点指向下一个结点的指针），以及结点构造函数，具体代码如下：
struct LinkedNode
{
int val;
LinkedNode* next;
LinkedNode(int val):val(val),next(nullptr){}
};
其次，在这个类里面，定义两个变量，分别是虚拟头结点（vhead）和链表长度（size），方便之后操作，具体代码如下：
private:
int size;
LinkedNode* vhead;
最后，也就是我们最关键的一步，链表的初始化，初始化的内容一共有两个，分别是把size初始化为0，为vhead创建空间，具体代码如下：
MyLinkedList() {
vhead=new LinkedNode(0);
size=0;
}
2.2 返回指定下标结点的值
获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
分析：我们知道，在一个链表中，若想获得某个位置的元素，我们需要从前往后查找，具体思路如下：
1.首先判断所给下标是否合法
2.定义一个cur指针进行查找，切记不能轻易移动头结点，因为该链表不是循环链表也不是双向链表，只有next指针，也就是说只能找到下一个结点，一旦改变了头结点，就不能回去，所以我们定义一个cur指针遍历
3.当index>0时，往后循环并进行index--操作，这里可能粗心会写错，我们可以以头结点为例检查是否正确：
头结点index=0，不进入while循环，直接返回虚拟头结点的后继，正确。
本题的源代码如下
int get(int index) {
LinkedNode *cur=vhead->next;
//判断所给下标是否合法
if(index<0||index>(size-1))
return -1;
else
{
while(index>0)
{
cur=cur->next;
index--;
}
return cur->val;
}
}
2.3在链表头尾、指定位置插入元素
其实这三个插入本质思路是一样的，都是通过遍历寻找前驱结点，然后更改指针指向，并且size++（这个一定不要忘记！）不同的是，在链表头插入元素的前驱是知道的，即vhead，在链表尾部插入元素找到var->next=NULL即可，而在指定位置插入元素，则要根据index去查找这个位置的前驱结点，代码如下：
void addAtHead(int val) {
LinkedNode *newhead=new LinkedNode(val);
newhead->next=vhead->next;
vhead->next=newhead;
size++;
}
void addAtTail(int val) {
LinkedNode *newtail=new LinkedNode(val);
newtail->next=NULL;
LinkedNode *cur=vhead;
while(cur->next!=NULL)
cur=cur->next;
cur->next=newtail;
size++;
}
void addAtIndex(int index, int val) {
if(index<0||index>size)
return;
else
{
LinkedNode* temp=new LinkedNode(val);
LinkedNode* cur=vhead;
while(index>0)
{
cur=cur->next;
index--;
}
temp->next=cur->next;
cur->next=temp;
size++;
}
}
2.4删除指定下标和删除指定元素
同样，和插入一样，删除的思路也是找到要删除结点的前驱结点，对于删除指定下标，首先要判断下标是否合理，后续操作都差不多，寻找要删除的结点，删除后记得释放这个结点的空间，最后不要忘记改变size，代码如下：
删除指定下标
void deleteAtIndex(int index) {
//这里是or不是and，写的时候粗心打错了，判断下标是否合理
if(index<0||index>(size-1))
return;
else
{
LinkedNode* cur=vhead;
while(index>0)
{
cur=cur->next;
index--;
}
//要删除的结点temp
LinkedNode* temp=cur->next;
cur->next = cur->next->next;
//C++需要手动释放
delete temp;
temp=nullptr;
//最后不要忘记size--；
size--;
}
}
删除指定元素:
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//设置虚拟头结点
ListNode* vhead=new ListNode(0);
vhead->next=head;
ListNode* cur=vhead;
//while循环要判断，不然后面会报错
while(cur->next!=NULL)
{
if(cur->next->val==val)
{
ListNode* temp=cur->next;
cur->next=cur->next->next;
delete temp;
}
//这里要记得更新cur指针
else
{
cur=cur->next;
}
}
return vhead->next;
}
};
以上是设置虚拟头结点的指定元素的删除，下面是不设置虚拟头结点的指定元素的删除：
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//不设置虚拟头结点
//1.讨论如果要删的结点是头结点
while(head!=NULL&&head->val==val)
{
ListNode* temp=head;
head=head->next;
delete temp;
}
//2.讨论如果要删的节点不是头结点
ListNode* cur=head;
while(cur!=NULL&&cur->next!=NULL)
{
if(cur->next->val==val)
{
ListNode* temp=cur->next;
cur->next=cur->next->next;
delete temp;
}
//不要忘记加else！！！
else
cur=cur->next;
}
return head;
}
不设置虚拟头结点的话，就要讨论所要删除的那个元素是不是head，head是没有前驱的，所以直接把指针往后移动一位然后释放掉head就可以了。
2.5反转链表
反转链表一共有两种方法，一种是双指针法，一种是递推法，但是递推法的本质思路也是双指针法，下面我将一一介绍这两种方法：
2.5.1双指针法
双指针法，顾名思义，就是定义两个指针pre和cur，pre指向cur的前驱结点，然后交换结点的指针方向，但是这里有一个问题，cur的后继指向pre之后，我们就找不到cur的后继节点了，因此我们需要再创建一个temp指针，记录cur的后继节点（我觉得这个应该叫三指针法（手动狗头））。
修改过指针方向之后，把cur赋值给pre，把temp赋值给cur（这里赋值的顺序不能改变！！！一旦改变，两者就都会变成temp）。
写代码的时候依旧要注意循环的条件是什么，我们可以知道，当cur==NULL时，说明pre已经指向了最后一个结点，前面的结点都已经修改完了
代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
//双指针法
ListNode* pre=NULL;
ListNode* cur=head;
ListNode* temp;
//注意循环条件
while(cur!=NULL)
{
temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
};
2.5.2递归法
递归法实际上就是根据双指针法修改的，建立一个reverse函数，来改变两个指针之间的方向，同样是cur==NULL时，返回pre，如果不是的话，先改变指针方向，然后让cur为pre，temp为cur，进入下一层递归，初始递归pre为NULL，cur为head，代码如下：
class Solution {
public:
//递归法
ListNode* reverse(ListNode* pre,ListNode* cur)
{
if(cur==NULL) return pre;
else
{
//记录后继节点
ListNode* temp=cur->next;
//更改指针方向
cur->next=pre;
//这里的return不要忘记加上
return reverse(cur,temp);
}
}
ListNode* reverseList(ListNode* head) {
//初始递归
return reverse(NULL,head);
}
};
3.总结反思
1.我对链表的创建不是很熟练，结构体后要加分号，链表的创建要记下来，在class类里可以定义size和vhead，以及c++不仅要手动delete，还要让temp=nullstr。
2.有时候还会粗心把and和or写错，并且老是忘记size的操作。
3.递归法如果需要return的话一定要记得return。
4.每层循环里一定要记得更新cur，这个我老是忘记。
5.设置虚拟头结点明显让操作更简单，但也要学会不设置虚拟头结点怎么写。
6.终于把C++链表弄懂了，真的好有好有成就感！！！