西宁做网站建设公司/搜索引擎排名google

一、问题概述

对于一个单向链表，要找到中间值的话，我们可以使用节点个数除以2的方式，然后循环N/2次来找到中间节点；
还有一种方式就是使用快慢指针的方式，定义两个指针，快指针速度是慢指针的两倍，这样同样的时间下，快指针的路程就是慢指针的两倍，也就是说，当快指针到最后的节点时，慢指针指向的就是中间节点，注意当节点数是偶数的时候，指向的是中间部分的右边一个节点，当节点数为奇数时候，就是指向的中间节点。

二、代码实现

package mypackage;//测试
public class MyJava {//节点类private static class Node<T> {T data;Node next;//构造方法public Node(T data, Node next) {this.data = data;this.next = next;}}//    查找中间值的方法,注意要到时候要传入第一个节点public static Integer getmid(Node node){
//        定义快慢指针Node fast=node;Node slow=node;
//        快指针不是null,且下一个节点也不是null的情况下
//        让快指针每次走两步，慢指针每次走一步
//        当快指针到最后的节点时，慢指针指向的就是中间节点
//        注意当节点数是偶数的时候，指向的是中间部分的右边一个节点
//        当节点数为奇数时候，就是指向的中间节点
//        思考1：为什么要(fast!=null)&&(fast.next!=null)两个判断条件
//        思考2：为什么(fast!=null)要在前，(fast.next!=null)要在后
//        思考3：为什么要&&，而不是使用&while((fast!=null)&&(fast.next!=null)){
//        while((fast.next!=null)&&(fast!=null)){
//            两个next就是模拟两步fast=fast.next.next;slow=slow.next;}
//        跳出循环表示快指针到最后的节点了return (Integer) slow.data;}public static void main(String[] args) {
//        创建节点，采用这样的方式创建Node<Integer> a=new Node<Integer>(1,null);Node<Integer> b=new Node<Integer>(2,null);Node<Integer> c=new Node<Integer>(3,null);Node<Integer> d=new Node<Integer>(4,null);Node<Integer> e=new Node<Integer>(5,null);Node<Integer> f=new Node<Integer>(6,null);Node<Integer> g=new Node<Integer>(7,null);//        节点指向性a.next=b;b.next=c;c.next=d;d.next=e;e.next=f;f.next=g;
//        调用方法Integer mid=getmid(a);System.out.println("中间节点的数据为："+mid);}
}

结果为4，确实是中间节点：

三、思考点

• 思考1：为什么要(fast!=null)&&(fast.next!=null)两个判断条件
• 思考2：为什么(fast!=null)要在前，(fast.next!=null)要在后
• 思考3：为什么要&&，而不是使用&

这几个问题要一起解答，在这之前了解一下什么是空指针异常？
什么是空指针异常？

• 所谓的指针，就是java中的对象的引用。比如String s;这个s就是指针
• 所谓的空指针，就是指针的内容为空，比如上面的s,如果令它指向null,就是空指针
• 所谓的空指针异常，就是一个指针是空指针，你还要去操作它，既然它指向的是空对象，它就不能使用这个对象的方法。比如上面的假如为null,你还要用s的方法，比如s.equals(String x);那么就会产生空指针异常。

回到问题，因为fast步长为2，当节点数为奇数的时候，经过一定的次数，fast一定是在最后一个节点，然后经过(fast.next!=null)判断就会跳出循环，此时(fast!=null)确实是多余的；

但是当节点数为偶数的时候，经过一定的次数，fast一定是在最后一个节点的后一个节点，什么意思呢，就是这个时候fast一定是移动到null的，那么此时还可以使用(fast.next!=null)判断吗，好像是可以的，但是并不可以，因为会出现NullPointerException错误，这个错误就是空指针异常，null.next是什么？对null调用任何方法都会造成NullPointerException错误。

那么怎么办呢，只有一个办法，就是让(fast.next!=null)不执行，那么怎么判断循环结束呢，就需要使用(fast!=null)了，因此两个条件都是需要的，并且为了不出现NullPointerException错误，让(fast.next!=null)不执行，得使用&&与符号，这个符号当前一个条件为false时，直接就跳出循环了，不会再执行后一个条件，而单个＆符号则不会有短短路的功能，即使前一个条件已经判断为false后一个条件还是会判断。另外使用&&时，(fast!=null)要在前，(fast.next!=null)要在后 ，这样当(fast!=null)条件能跳出循环的时候，(fast.next!=null)就不会再执行了，就不会出现NullPointerException了。

错误案例1

节点改为偶数个，只创建6个节点即可，判断条件改为(fast!=null)&(fast.next!=null)，运行结果如下：

错误案例2

节点改为偶数个，只创建6个节点即可，判断条件改为(fast.next!=null)&&(fast!=null)，运行结果如下：

错误案例3

节点改为偶数个，只创建6个节点即可，判断条件改为(fast.next!=null)，运行结果如下：