关于链表的基本操作和一些LeetCode题目集合
目录
删除结点的步骤
方法一 删除头结点时另做考虑
方法二 添加虚拟头节点
方法三 递归法
三种方法的比较：
删除结点的步骤
找到该结点的前一个结点进行删除操作。
具体删除方式：我们假设要删除的节点是 i ,那我们只需要找到 i 的前驱 p , 然后让 p -> next = p -> next -> next，这样就跳过了 i 这个节点，自然也就实现了删除的目的。
但是这个方法需要找到被删除节点的前驱，对于头结点（也就是第一个节点）来说， 他是没有前驱的，需要特殊处理。下面介绍的方法，第一种是把头结点单独拿出来考虑，第二种是加了一个虚拟头结点，都解决了这个问题。
方法一 删除头结点时另做考虑
删除头结点和删除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来删除当前节点，而头结点没有前一个节点。
所以头结点如何删除呢，其实我们只要将头结点向后移动一位就可以，这样我们就从链表中删除了一个头结点。
别忘将原头结点从内存中删掉。
没有释放内存的代码版本：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//处理头指针的问题
while (head!=NULL && head->val==val){
head=head->next;
}
//特判下链表是否为空（可能全删没了）
if (head==NULL) return NULL;
//利用前驱进行删除操作
ListNode* p=head;
while (p->next!=NULL){ //看下一个
if (p->next->val==val){ //如果需要删除
p->next=p->next->next; //指针p不动，直接跳过删除的元素
}else p=p->next; //不需要删除，p移动
}
return head;
}
};
释放内存的代码版本：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
while (head!=NULL && head->val==val){
ListNode* q=head;
head=head->next;
delete q;
}
if (head==NULL) return NULL;
ListNode* p=head;
while (p->next!=NULL){
if (p->next->val==val){
ListNode* q=p->next;
p->next=p->next->next;
delete q;
}else p=p->next;
}
return head;
}
};
方法二 添加虚拟头节点
在上面的方法中，我们需要单独去处理删除的元素在头指针位置的情况，那么可不可以 以一种统一的逻辑来删除链表的节点呢。
其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。
我们来给链表添加一个虚拟头结点dummyNode为新的头结点，此时我们要移除这个旧头结点元素1。
这样就可以使用和移除链表其他节点的方式统一了。照旧，还要delete内存。
最后呢在题目中，return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//定义一个虚拟头结点，指向head
ListNode* dummyNode=new ListNode;
dummyNode->next=head;
//从虚拟头结点开始 进行删除
ListNode* p=dummyNode;
while (p->next!=NULL){
if (p->next->val==val){
p->next=p->next->next;
} else p=p->next;
}
//最后再忽略掉虚拟头指针
return dummyNode->next;
}
};
方法三 递归法
以上两种方法都算是手工模拟，下面介绍的递归法更加优美。
链表具有天然的递归性
可以把上图中的第二个链表看成节点 0 后面挂接了一个更短的链表，比第一个链表少了一个节点（节点 0 ）； 这个更短的链表可以看成 1 作为头节点的链表，这个更短的链表可以继续看成节点 1 后面挂接了一个更更短的链表（缺少节点 1）； 这个更更短的链表可以看成 2 作为头节点后面挂接了一个更更更短的链表（缺少节点 2），依次类推。
有了这样的思考，链表中的很多操作，都可以使用递归这种逻辑思维方式来完成。
如上图示，如果头节点对应的数值不等于 val ，原问题的结果就是头节点 加上 后面子问题求得的解，否则，结果就是子问题的解。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (head==NULL) return NULL;
ListNode *p=removeElements(head->next,val);
if (head->val==val) {
return p;
} else {
head->next=p;
return head;
}
}
};
首先递归出口肯定是head==NULL， 然后是阶段性的求出每个子问题的解，这里难点在于返回。
之前写的是 if (head->val == val) return p; else return head; 这句话乍看上去没毛病，如果相等的话，那么这个节点是要删除的，所以这个子问题的答案就是忽略了head的下一个子问题的答案，也就是求出来的p； 如果这个点需要保留的话呢，这个head是需要保留的，返回head+p。
但是具体执行的时候发现，这个链表并没有被改变，一但返回一次head，就前功尽弃了，因为head的指针没有修改，那怎么实现返回head+p？
修改指针，所以代码第9行是最关键的一个语句，head原本指向下一个，现在让它指向的是子问题的解p，也就是这一语句，实现了删除的功能。
如图，答案p是我们就好的子问题的解，如果这个head要删除，我们确实只需要返回p，但是当一个head被保留的时候，我们是需要重构指针的，也就是把head指向了子问题的解，这才跳过了被删除的元素。
三种方法的比较：
对于方法一二，头指针有特殊性，需要单独考虑，在递归法中，就没有这个烦恼。
方法一二中，只有当一个元素被删除，才需要修改它前驱的指针，而递归法中的指针修改操作则恰恰相反，一个元素需要删除，指针不变 ，一个元素被保留，就需要改变一下指向，也就是第九行代码。
为什么需要这么频繁的指针修改操作，因为对于一个head来说，尽管可能他的next原本就是p，但是它无法判断到底是不是，他不能确定子问题的解的头指针还是不是它的next，所以每次都需要重新将head指向一遍p。
假如删除4，红色为指针的重覆盖。