[数据结构与算法]【java版数据结构】快慢指针找单链表中间值

链表不像顺序结构的数组那般可通过指定的下标访问中间值，我们通过指定一个快指针（步长为2，指针每次往下移动两位），一个慢指针（步长为1，指针每次往下移动一位），当快指针遍历完整个链表时，慢指针刚好指向链表的中间元素，以此原理，我们也能找到链表中的其他结点。

原理：
这就类似时间相同，速度和路程成正比，快指针的速度是慢指针的两倍，当快指针走完全程（单位1）时，慢指针刚好走到全程的1/2

图片描述：

为了防止空指针异常，以及当链表个数是偶数，该方法也适用，我们在遍历快指针时加上了一个安全验证，快指针本身不为空，fast!=null。

 //获取中间元素
    public  static Node getMid(Node first){
        //定义两个快慢指针
        Node fast=first;
        Node slow=first;
        //遍历链表，定义指针的移动速度
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        // 当快指针走完全程，慢指针就指向中间元素
        return slow;
    }

测试代码：

public class FastSlowTest {
    public static void main(String[] args) {
       //创建结点
        Node first=new Node("aa",null);
        Node second=new Node("bb",null);
        Node third=new Node("cc",null);
        Node fourth=new Node("dd",null);
        Node fifth=new Node("ee",null);
        Node sixth=new Node("ff",null);
        Node seventh=new Node("gg",null);
        Node eighth=new Node("hh",null);

			//建立连接
        first.next=second;
        second.next=third;
        third.next=fourth;
        fourth.next=fifth;
        fifth.next=sixth;
        sixth.next=seventh;
        seventh.next=eighth;

        Node mid = getMid(first);
        System.out.println("中间的结点是"+mid.item);

    }

    //获取中间元素
    public  static Node getMid(Node first){
        //定义两个快慢指针
        Node fast=first;
        Node slow=first;
        //遍历链表，定义指针的移动速度
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        // 当快指针走完全程，慢指针就指向中间元素
        return slow;
    }

	//构造内部类描述链表的结点
    private static class Node<T>{
    		//不确定的某一类型
        T item;
        Node next;
			//构造方法
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

}