虚拟头指针，在当前head的前面建立一个虚拟头指针，然后哪怕当前的head的val等于提供的val也能进行统一操作
203移除链表元素简单题
/**
* 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) {
//为了统一操作，创建虚拟头指针
ListNode fakehead=new ListNode();
//虚拟头指针指向head，然后做判断
fakehead.next=head;
ListNode current=fakehead;
while(current.next!=null)
{
//只要头指针的next不是空指针，等于val就删除，不等于就指向下一个指针
if(current.next.val==val)
{
current.next=current.next.next;
}
else
{
current=current.next;
}
}
return fakehead.next;
}
}建立虚拟头指针fakehead，用空构造函数建造就可以，将fakehead的next指向head
用current指向fakehead开始遍历链表，从head开始进行判断，cur的next的val值和提供的目标值一样就进行移除操作，否则移动指针指向cur的next指针。
707设计链表中等题
这道题非常考察链表的基本操作，沿用203题，为了进行单链表的统一操作，本题用虚拟头结点
class MyLinkedList {
//构建链表ListNode
class ListNode{
int val;
ListNode next;
ListNode(int val)
{
this.val=val;
}
}
//建立虚拟头结点
private ListNode fakehead;
//记录链表总长度
private int nodelen;
public MyLinkedList() {
this.fakehead=new ListNode(0);
this.nodelen=0;
}
public int get(int index) {
//查找下标为index的val
if(index<0 || index>=nodelen)
{
return -1;
}
ListNode current=fakehead;
//找到index+1
for(int i=0;i<=index;i++)
{
current=current.next;
}
return current.val;
}
public void addAtHead(int val) {
//虚拟头指针后面增加一个元素
ListNode newnode=new ListNode(val);
newnode.next=fakehead.next;
fakehead.next=newnode;
nodelen++;
}
public void addAtTail(int val) {
//因为要在尾巴插入，所以要记录链表的总长度
ListNode newnode=new ListNode(val);
ListNode current=fakehead;
while(current.next!=null)
{
current=current.next;
}
//现在指向最后的元素了
current.next=newnode;
nodelen++;
}
public void addAtIndex(int index, int val) {
if(index<0 || index>nodelen)
{
return;
}
ListNode newnode=new ListNode(val);
ListNode current=fakehead;
//插入到index前面
for(int i=0;i<index;i++)
{
current=current.next;
}
newnode.next=current.next;
current.next=newnode;
nodelen++;
}
public void deleteAtIndex(int index) {
if(index<0 ||index>=nodelen)
{
return;
}
ListNode current=fakehead;
for(int i=0;i<index;i++)
{
current=current.next;
}
current.next=current.next.next;
nodelen--;
}
}- 首先为了初始化链表，我们需要写一个链表类，然后定义两个成员变量fakehead（虚拟头指针）和nodelen（链表中元素的个数），初始化的时候fakehead定义为val为0的链表元素，nodelen为0
- 根据索引index去get一个元素的val值，首先要判断index是不是小于0或者大于等于nodelen（当前的元素值索引最大只能是nodelen-1），然后从i=0遍历到index+1就可以，因为是从虚拟头结点开始遍历的
- 在第一个元素添加很简单，就是虚拟头指针原来的next变为新添加元素的next，虚拟头指针的next指向新添加元素就可以了
- 在尾部添加元素，只需要一直遍历指针指向最后一个元素然后next设为新添加元素
- 给定索引index和val，在index元素的前面插入新元素，我们需要找到前置链表元素的位置，然后进行添加操作，用for循环遍历的时候，就需要遍历到index-1下标的元素位置
206反转链表简单题
/**
* 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;
ListNode cur=head;
//交换用
ListNode temp=null;
//前置指针先指向null
while(cur!=null)
{
temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
return pre;
}
}双指针思想，设置pre为前置指针，让cur一直指向pre，就相当于反转了链表
注意：pre循环的时候要指向cur，而cur为了能指向本来的next，需要建立一个链表指针temp来保存
24两两交换链表中的节点 中等
虚拟头指针+两个temp链表进行交换
/**
* 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 fake=new ListNode();
fake.next=head;
ListNode cur=fake;
ListNode temp1=new ListNode();
ListNode temp2=new ListNode();
while(cur.next!=null && cur.next.next!=null)
{
//满足交换条件
temp1=cur.next;
temp2=cur.next.next.next;
//f-c
cur.next=cur.next.next;
//f-2-1
cur.next.next=temp1;
//f-2-1-3
cur.next.next.next=temp2;
cur=temp1;
}
return fake.next;
}
}19删除链表的倒数第N个节点 中等
/**
* 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 removeNthFromEnd(ListNode head, int n) {
//虚拟头指针
ListNode fake=new ListNode();
fake.next=head;
//设置双指针
ListNode slow=fake;
ListNode fast=fake;
//先让fast移动到第n个位置
for(int i=0;i<n;i++)
{
fast=fast.next;
}
//再两个一起移动
while(fast.next!=null)
{
fast=fast.next;
slow=slow.next;
}
//删除slow后面的节点
slow.next=slow.next.next;
return fake.next;
}
} 
用快慢双指针完成这个问题，虚拟头指针方便统一操作，slow的下一个指标对应的元素就是要删除的元素
142环形链表
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
//检查有没有环，快慢指针，快指针移动两个元素，慢指针一次移动一个元素，如果有环一定会相遇
ListNode fast=head;
ListNode slow =head;
while(fast!=null && fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
if(slow==fast)
{
//相遇了,记录相遇节点
ListNode index1=slow;
//设入口到head距离为x，环入口到相遇节点为y，相遇节点到入口的节点数是z
//则有2(x+y)=x+y+n(y+z)等价于x=n(y+z)-y等价于x=(n-1)(y+Z)+z
//由于n至少转了一圈以上，fast才能够追上slow，所以只要一个指针从head出发，一个指针从相遇节点出发，最终相遇的地方就是环的路口
ListNode index0=head;
while(index0!=index1)
{
index0=index0.next;
index1=index1.next;
}
return index0;
}
}
return null;
}
}- 快慢指针入手，快指针每次移动两个下标，慢指针每次移动一个，如果有环，必定相遇，由于快指针每次移动两个，所以while循环的条件是他现在和next都不为null
- 如何判断出口，就要用数学公式进行判断，根据相遇的时候，快指针移动节点的个数是慢指针移动节点个数的二倍，列出等价公式，得到x=(n-1)(y+z)+z
- 这说明从相遇节点出发无论快指针是走了一圈y+z的路程还是很多圈，最终都会和从head出发的指针相遇，而这个相遇的地点就是环的入口指针
- xyz示意图
