- 移除链表元素
- 设计链表
- 翻转链表
- 两两交换链表中的结点
移除链表元素
ps：有时候感觉到底要不要写特判，你想到了就写！因为一般特判有一劳永逸的作用。
解法有两种，一种是不用虚拟头结点，另一种就是用虚拟头结点。
这里我习惯用虚拟头结点。不用虚拟头结点就需要自己写头结点的特判。
虚拟头结点的好处：方便对每个结点进行统一处理，不用写特判。
解法：双指针
链表的删除操作并不是要找目标元素才能完成删除，而是找目标元素的前一个元素才能完成删除。所以需要一个pre用于指向目标元素的前一个元素，cur用来指向目标元素。
算法流程
cur指针进行判断，如果不是cur指向的不是目标元素，双方一起往后走。pre = cur。cur = cur.next。
如果cur指的是目标元素，那么就要完成上面图里面的操作。
pre的next应该指向cur的后面那个元素，所以是pre.next = cur.next。
此时你的pre还在原地，然后cur指的那个元素被删了，然后就后移。
对于写代码：
可以发现不管是不是目标元素，cur始终是要后移的。而pre如果是cur指目标元素后才后移，如果不是目标元素，就一起后移。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null){
return head; //空链表判断
}
//链表不空，进入下面的移除逻辑
ListNode dummy = new ListNode(-1,head); //初始化虚拟头结点
ListNode pre = dummy; //由于要进行删除操作，pre应该指向虚拟头结点。
ListNode cur = head; //cur用于遍历，用于寻找目标结点。
while(cur!=null){ //遍历结点不为null
if(cur.val==val){ //如果等于目标结点
pre.next = cur.next; //前一个结点的后驱指向遍历结点的后驱，因为此时这个cur指向的元素是要删除的
}else{
pre = cur; //这个就是不等于目标结点，就两者同时后移
}
cur = cur.next; //不管如何，cur始终在进行遍历，所以要一直后移。
}
return dummy.next; //返回虚拟头结点的后一个结点，就是答案。
}
}
设计链表
都是链表的基础操作，需要注意的地方就是题目的要求。
这个题是一个非常好的模板。一定要擅长写模板。
本题为了操作方便，所以用了虚拟头结点作为默认初始化
class ListNode{ //结点类。这个数据结构一定要会写
int val;
ListNode next;
ListNode(){}
ListNode(int val,ListNode next){
this.val = val;
this.next = next;
}
ListNode(int val){
this.val = val;
}
}
class MyLinkedList { //定义i链表
//链表两个属性：1.长度和最开始的结点
//但是注意这里链表的第一个结点是虚拟头结点
//这么设计是为了方便统一操作。
int size;
ListNode head; //注意这是虚拟头结点
//初始化链表，长度为0，然后创建了一个虚拟头结点。
//所以一定要注意后续的操作的两个细节
//此时链表第一个结点是虚拟头结点，但是我并不把它计入链表长度
//然后链表元素下标是从0开始的。后续对index循环那里很重要，小心坑。
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
//
public int get(int index) {
if(index<0 || index>=size){ //因为下标从0开始，所以index=size也会判错
return -1;
}
//创建一个遍历指针，注意这里是指的虚拟头结点。所以后面边界才是<=index
ListNode currentNode = head;
//开始遍历查找
for(int i = 0;i<=index;i++){ //就是因为从虚拟头结点开始，而且结点又是从下标0开始。所以才是取等。相当于多+1
currentNode = currentNode.next;
}
//最后currentNode会停在index的位置。
return currentNode.val;
}
public void addAtHead(int val) {
addAtIndex(0,val); //这就是下面一般情况的应用，由于我是用的带虚拟头结点，所以可以当一般情况来处理。
}
public void addAtTail(int val) {
addAtIndex(size,val);//这就是下面一般情况的应用，由于我是用的带虚拟头结点，所以可以当一般情况来处理。
}
public void addAtIndex(int index, int val) {
//先进行特判 当下标大于链表长度，则不执行插入
if(index > size){
return;
}
if(index<0){ //当下标长度为负值，插入到第一个元素，所以这里进行下标的重新修改
index = 0;
}
size++; //要插入，那么链表长度+1
ListNode pre = head; //由于要插入到目标之前，所以pre是初始化为虚拟头结点。
for(int i = 0;i<index;i++){//由于是要插入到index元素之前，而pre一开始是在虚拟头结点。所以这样会导致pre最终停在index元素之前的那个元素。
pre = pre.next;
}
ListNode insertNode = new ListNode(val); //定义新插入的结点，这里用一参构造，next默认初始化为null了
insertNode.next = pre.next; //插入操作：新结点的next指向pre的后面那个元素
pre.next = insertNode; //pre再指向新插入的结点。
}
public void deleteAtIndex(int index) {
//先对index是否有效进行检查
if(index < 0 || index>=size){ //下标小于0或者是下标大于或等于链表长度，由于是从0开始，所以等于size也是无效索引。
return;
}
size--;//删除元素就可以先长度--，因为过了特判就进入了删除逻辑，一定有元素删除
ListNode pre = head;//删除就必须要找目标元素的前一个元素，所以从虚拟头结点开始最方便
for(int i = 0;i<index;i++){//由于下标从0开始，而pre一开始在虚拟头结点，所以pre最终停在index的前一个位置
pre = pre.next; //不断后移找目标元素的前一个元素
}
pre.next = pre.next.next; //进行删除操作
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
一定要注意题目要求：带虚拟头结点，而且虚拟头结点不计入链表长度。并且下标从0开始。
翻转链表
注意：没有用到虚拟头结点
这个题怎么想：
首先拿到一个链表：
1 -> 2 -> 3 -> null
翻转链表那就是变成3 -> 2 -> 1 -> null
那很容易就能想到，把指针方向翻转就完成了修改。那就往这个方向去做。
如何完成修改，这里采用双指针，加一个tmp指针用于后移的方法。
pre一开始指向null，这里可以理解为在翻转过程中，那么第一个结点的next那必然是null。
cur用于遍历构造。
此时想到cur.next = pre ，那不就完成了next后驱的翻转，但是还有个问题，如果直接cur.next = pre，那就找不到后面的结点，无法继续遍历修改链表了。所以这里再加一个tmp用于存往后遍历的位置，这个tmp的值显然就是cur的后驱:cur.next。
所以现在来看完整的过程：
先用tmp记录cur的后驱。方便之后后移。
然后现在就可以放心的改指针了。
cur.next = pre。
然后pre也要后移，因为之后还有进行cur.next = pre来进行指针修改。你不后移之后不就改不了了。
pre = cur;
然后cur进行后移到tmp。
从这个过程往后走，cur最终会走到null上，pre最终停留在最后一个结点。所以循环终止条件就是cur!=null,最后返回pre。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null; //由于要倒过来，所以pre指在null用于cur改后驱指向。
ListNode cur = head; //cur指向head用于遍历
while(cur!=null){
ListNode tmp = cur.next; //用tmp记录后继，方便改指针之后的后移
cur.next = pre; //翻转指针
pre = cur; //翻转成功后，前向指针进行后移
cur = tmp; //遍历指针后移
}
return pre;
}
}
两两交换链表中的结点
方法：迭代
思路出发：从模拟的角度来
本题是要加虚拟头结点的。因为这更方便处理。上一题就不用加，因为太简单了。对极端情况不敏感还是用虚拟头结点比较好。
现在想完成两两交换，那就直接按图来即可。
这里目的是node1，node2完成结点交换。
显然temp.next指向node2，这样node2就到node1的位置来了。
然后node1现在要作为第二个结点，那就node1指向node2的next结点。
现在node2的next再指向node1即可。
现在得到
前两个就已经改完了，那么现在就要到下一轮，显然temp要变到node1的位置，然后开启下一轮的逻辑。
最后返回的结果是dummyhead.next
所以现在还剩下两个问题:
1、node1和node2如何定义？
很简单，node1就是temp.next即node1 = temp.next
node2就是temp.next.next即node2 = temp.next.next
2、循环什么时候停止。
思考的突破口在于后移操作，因为在后移的过程中非常害怕空指针。所以后移的空指针是处理就是循环终止的关键。
后移与否就要考虑后面的指针空不空,而且一开始我的temp在虚拟头结点上。
所以循环条件就是:
while(temp.next!=null && temp.next.next!=null)
不能往后移了，代表循环该停了。
如果对极端情况有疑问，把上面那个图截取一部分思考即可。效果是一样的。这就是虚拟头结点的统一处理效果。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyhead = new ListNode(0);//创建一个虚拟头结点
dummyhead.next = head; //把虚拟头结点加到链表的头部去
ListNode temp = dummyhead; //创建迭代的指针temp。
while(temp.next!=null && temp.next.next!=null){
ListNode node1 = temp.next; //定义node1
ListNode node2 = temp.next.next; //定义node2
//开始进行交换操作，下面三行代码看图来做很清晰
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
//注意是指向node1，因为node1被换到了后面去。
temp = node1;
}
return dummyhead.next;
}
}
这里我还发现一个习惯，一般迭代操作，都习惯去创建一个遍历指针去迭代。这样更加方便，原本代表链表的指针不要动，可以用来做结果的返回。
