1. 环形链表（经典中的经典），返回入环节点，那么我们应该怎么做呢，首先判断链表有没有环，然后是不是空，用经典的快慢指针，快的指针一次走两步，慢的指针走一步，问题一：先想一下，为什么fast的速度设置为2，slow的速度为1
假如两个有环，他们俩个一定会相遇，因为在环中，fast相当于比slow永远多走一步，也就是说，fast相当于在环里面一直走，slow一直保持原有的位置没有动，所以一定会相遇，所以fast的速度为2在环中会一定和slow相遇
问题二后面的代码是什么意思（不明白看我的图）
fast的速度一直是slow的二倍，所以肯定路程也是二倍（保姆级教学
）
L是头到环入口的距离，环入口到相遇点的距离是X，M是相遇点到环的入口的距离
力扣142
public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast=head; ListNode slow =head; ListNode cur =head; if(head==null){ //判断是否为空 return null; } while(fast!=null&&fast.next!=null){//如果没有环，那么一定会有空的时候 fast=fast.next.next; slow=slow.next; if(slow==fast){ //把它放后面很细节，是为了不让fast和slow等于头退出 break; } } if(fast==null||fast.next==null){ //判断是否有环 return null; } while(slow!=cur){ //找环的入口点 cur=cur.next; slow=slow.next; } return cur;
2.链表相交 很简单思路，把A，B链表走一遍，知道长度差，然后谁长，让谁先走，然后看相不相交
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode cur=headA; ListNode curv=headB; int la=0; //a表长度 int lb=0; //b表长度 if(headB==null&&headA==null){ return null; } if(headA==null&&headB!=null||headB==null&&headA!=null){ return null; } while(cur!=null){ //计算A与B的长度 la++; cur=cur.next; } while(curv!=null){ lb++; curv=curv.next; } cur=headA; //还原两个指针，让他们两个再次指向头 curv=headB; if(lb>la){ while(lb-la>0&&curv!=null){ //b长先走 curv=curv.next; lb--; } } else{ while(la-lb>0&&cur!=null){ cur=cur.next; //a长a先走 la--; } } while(cur!=null){ //很重要一个点，相交是点相同，不是点值相同 if(cur==curv){ //不要去写.val==.val是不对的 return cur; } cur=cur.next; curv=curv.next; } return null; } }
3.双向链表。要求会写，这是类的必须，其他类中的方法放到下面，内部类是必须要的，然后下面是链表具备的头和尾指针方便插入和删除，（需要分到两个部分写），
下面的各种函数你也都可以用phead就是像c语言那种传一个头之类的。
public class ListNode { public class LinkedNode{ int val; LinkedNode next = null; LinkedNode prev=null; LinkedNode(int val) { this.val = val; } } public LinkedNode head; //链表的头 public LinkedNode tail; //链表的尾巴
3.（1）头插
// 2、无头双向链表实现 //头插法 public void addFirst(int data){ LinkedNode p=new LinkedNode(data); 申请一个节点 if(head==null){ //之前的节点为空的话，就头和尾都在开始的节点 head=p; tail=p; } p.prev=null; //头节点的前面是NULL head.prev=p; //头连接P节点 p.next=head; head=p; //P成为新的头 tail.next=null; //尾节点下一个还是null }
（2）尾插
public void addLast(int data){ LinkedNode p=new LinkedNode(data); //还是生成个节点 if(head==null){ head=p; //头和尾都是空 tail=p; } while(tail.next!=null){ tail=tail.next; //尾巴遍历到最后 } tail.next=p; //tail的下一个连像尾巴节点p p.prev=tail; //p的前一个节点是尾巴 tail=p; //尾巴指向p }
（3）任意位置插入,第一个数据节点为0号下标，插入节点
public boolean addIndex(int index,int data) { if(index<0||index>size()){ //插入序列不合理 return false; } LinkedNode cur=head; LinkedNode p=new LinkedNode(data); int n=1; if(index==1){ //插入第一个就是头插 addFirst(data); } while(n<index){ n++; //找到要插入节点的前面 cur=cur.next; } if(cur.next.next!=null) { p.next=cur.next; //插入中间节点 p.prev=cur; //P的前驱后继 cur.next.prev=p; cur.next=p; //前驱节点的下一个连接他 } else { addLast(data); //最后一个就是尾插 } return true; }
（4）看关键字key在不在链表中（简单的遍历）
//查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ LinkedNode cur=head; while(cur!=null){ if(cur.val==key){ return true; } cur=cur.next; } return false; }
（5）//删除第一次出现关键字为key的节点
//删除第一次出现关键字为key的节点 public void remove(int key){ LinkedNode cur=head; while(cur!=null){ if(cur.next.val==key){ break; } } cur.next.prev=null; //key值的前一个点，的前指针为空 cur.next.next.prev=cur; //key的后一个节点连key前面的节点 cur.next=cur.next.next; //key值的前一个点下一个连接key值的下一个 }
（6）删除所有值为key的节点（删除全部和上面的删除一个意思一样）
public void removeAllKey(int key){ LinkedNode cur=head; while(cur!=null){ if(cur.next.val==key){ cur.next.prev=null; cur.next.next.prev=cur; cur.next=cur.next.next; } } }
（7）链表长度和展示（简单不解析了）
//得到单链表的长度 public int size(){ LinkedNode cur=head; int n=0; while(cur!=null){ cur=cur.next; n++; } return n; } public void display(){ LinkedNode cur=head; while(cur!=null){ System.out.println(cur.val); cur=cur.next; } }
