给定一个单链表，只给出头指针h：
1、如何判断是否存在环？
2、如何知道环的长度？
3、如何找出环的连接点在哪里？
4、带环链表的长度是多少？
解法：
1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。
2、对于问题2，记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度s。
3、问题3：有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。(证明在后面附注)
4、问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度
链表有环无环解决，寻找链接点。报错（显示在一个无环链做寻找连接点时，星标行出现空指针），使用其他人的有环无环判断代码后，成功。如下为错误代码：
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null||head.next==null||head.next.next==null||head.next.next.next==null) return null;
ListNode pre=new ListNode(0);
pre.next=head;
ListNode p=pre.next;
ListNode q=pre.next;
while(p!=null&&q.next!=null){
p=p.next;
q=q.next.next;
if(q==null)
return null;
if(q==p)
break;
}
//有环
ListNode preTem=head;
while(preTem!=null){
if(p==preTem)
return p;
preTem=preTem.next;
p=p.next;********************************
}
return null;
}
}
成功代码：
public ListNode detectCycle(ListNode head) {
if(head==null) return null;
ListNode slow=head;
ListNode fast=head;
do{
if(fast.next==null||fast.next.next==null)
return null;
fast=fast.next.next;
slow=slow.next;
}
while(fast!=slow);
ListNode temp=head;
while(temp!=null){
if(fast==temp)
return fast;
temp=temp.next;
fast=fast.next;
}
return null;
}
缺乏头节点时，添加头节点后，以后的对于链表的表示都用这个头节点来表示。
203题：删除一个结点。结点的赋值到底什么含义。。。。。
public static ListNode removeElements(ListNode head, int val) {
if(head==null) return head;
ListNode p=new ListNode(0);
p.next=head;
ListNode q=head;
while(q!=null){
if(q.val==val){
p.next=q.next;
q=null;//已经置为null，head却没改变。。。
q=p.next;
}else{
p=p.next;
q=q.next;
}
}
return head;
}//不通过，更改为下：通过
public ListNode removeElements(ListNode head, int val) {
if(head==null) return head;
ListNode p=new ListNode(0);
p.next=head;
ListNode q=head;
ListNode s=p;
while(q!=null){
if(q.val==val){
p.next=q.next;
q=null;
q=p.next;
}else{
p=p.next;
q=q.next;
}
}
return s.next;
}
如下也错
public static ListNode removeElements(ListNode head, int val) {
ListNode pListNode=new ListNode(0);
pListNode.next=head;
ListNode sListNode=head;
while(head!=null){
if(head.val==val){
pListNode.next=head.next;
head=null;
head=pListNode.next;
}else{
pListNode=pListNode.next;
head=head.next;
}
}
return sListNode;
}