数据结构之链表中的快慢指针

还是一样的初始化链表 a -> b -> c -> d -> e -> f -> g比如这个时候你定义了快指针为fastNode,慢指针为slowNode一开始将fastNode和slowNode都指向a这个时候判断有没有到链表尾部，很显然没有对吧那么这个时候fastNode指向了c，slowNode指向了b在判断fastNode有没有到尾部节点呢，依然是没有到对吧这个时候fastNode指向了e，slowNode指向了c在判断fastNode有没有到尾部节点呢 还是没有到继续 fastNode指向了g slowNode指向了d在判断的时候fastNode到链表尾部了，这个时候slowNode是不是就指向了链表到中间节点

package com.lilei.datastructure.linetable;import java.util.Iterator;/** * 单向列表 * * @author LiLei * @Classname LinkList * @Description TODO * @Date 2020/6/7 1:18 下午 */public class LinkList<T> implements Iterable<T> {    /**     * 链表节点的首节点     */    private Node head;    /**     * 链表节点中元素个数     */    private int size;    public LinkList() {        head = new Node(null,null);        size = 0;    }    /**     * 节点类，主要记录节点中存储对元素，和下一个节点的位置     */    private class Node<T> {        private T item;        private Node next;        public Node(T item, Node next) {            this.item = item;            this.next = next;        }    }    @Override    public Iterator iterator() {        return new LinkListIterator();    }    private class LinkListIterator implements Iterator<T> {        private Node next;        public LinkListIterator() {            this.next = head;        }        @Override        public boolean hasNext() {            return next.next != null;        }        @Override        public T next() {            next = next.next;            return (T) next.item;        }    }    public void clear() {        size = 0;        head.next = null;    }    public boolean isEmpty() {        return size == 0 && head.next == null;    }    public int length() {        return size;    }    public Node get(int i) {        if (i < 0 || i > size) {            throw new RuntimeException("获取位置元素不合法");        }        Node result = head.next;        for (int index = 0; index < i; index++) {            result = result.next;        }        return result;    }    public void insert(T t) {        Node node = head;        while (node.next != null) {            node = node.next;        }        Node<T> newNode = new Node<>(t, null);        node.next = newNode;        size++;    }    public void insert(int i, T t) {        if (i < 0 || i > size) {            throw new RuntimeException("插入位置有问题");        }        // 找到第i个位置的前驱节点        Node pre = head;        for (int index = 0; index < i; index++) {            pre = pre.next;        }        // A -> B        Node currentNode = pre.next;        Node newNode = new Node(t, currentNode);        pre.next = newNode;        size++;    }    public void remove(int i) {        if (i < 0 || i > size) {            throw new RuntimeException("删除位置有问题");        }        // 找到第i个元素的前一个元素        Node pre = head;        for (int index = 0; index < i; index++) {            pre = pre.next;        }        // 找到第i个元素后一个元素        Node next = pre.next.next;        // 将前一个元素指向后一个元素        pre.next = next;        size--;    }    public int indexOf(T t) {        Node next = head;        if (next.item.equals(t)) {            return 1;        }        for (int i = 0; i < size; i++) {            next = next.next;            if (next.item.equals(t)) {                return i;            }        }        return -1;    }    public void reverse() {        if (size == 0) {            return;        }        reverse(head.next);    }    private Node reverse(Node currentNode) {        // 如果遍历到最后一个节点，将head节点到next指向最后一个节点        if (currentNode.next == null) {            head.next = currentNode;            return currentNode;        }        // pre 链表中的每一个节点，从最后一个节点开始一直到第一个节点        Node pre = reverse(currentNode.next);        // 后面一个节点的next指向前面一个节点        pre.next = currentNode;        // 当前节点的下一个节点指向null        currentNode.next = null;        return currentNode;    }    public T getMid(Node firstNode) {        if (firstNode == null) {            return null;        }        Node<String> fastNode = firstNode;        Node<String> slowNode = firstNode;        // 当fastNode不为null的时候代表还没到链表到结尾        while (fastNode != null && fastNode.next != null) {            // fastNode比slowNode慢两倍的话，当fastNode到尾节点了，slowNode刚好到了中间            fastNode = fastNode.next.next;            slowNode = slowNode.next;        }        return (T) slowNode.item;    }

    public static void main(String[] args) {        LinkList<String> linkList = new LinkList();        linkList.insert(0, "test0");        linkList.insert(1, "test1");        linkList.insert(2, "test2");        linkList.insert(3, "test3");        linkList.insert(4, "test4");        linkList.insert(5, "test5");        linkList.insert(6, "test6");        for (String t : linkList) {            System.out.println(t);        }        System.out.println("=======================");        String midNodeValue =                linkList.getMid(linkList.get(0));        System.out.println(midNodeValue);    }}