Q：链表的中间元素

问题：如何得到一个链表的中间元素？

相信，这个问题对于刚入门编程的人来说，都不会难，最自然而然的想法是先遍历一遍链表，统计链表中的元素的个数，之后，再走一遍链表，所走的步长为链表长度的一半。这样就能获得链表的中间元素的值。但是，我们能不能有一种方法是只走一遍链表便得到结果的呢？当然是有的。不然我也不会写成博文总结学到的知识点了。哈哈哈哈~~(杠铃般的笑声)

一种比较有趣的解法是：

初始化两个指针a,b。其均指向链表的头节点处
a指针每次走一步，b指针每次走两步(a指针称为慢指针，b指针称为快指针)
当b指针直线末尾的时候，a指针所指向的节点便是链表的中间节点

具体代码如下：

/**

 * @author 学徒

 * 用于得到链表的中间元素

 */

public class MiddleNode {

    /**

     * 链表的节点

     *

     * @param <T> 链表的元素值

     */

    static class Node<T> {

        //节点值

        T value;

        //节点的下一个节点的指针

        Node<T> next;

        public Node(T value) {

            this(value, null);

        }

        public Node(T value, Node next) {

            this.next = next;

            this.value = value;

        }

    }

    /**

     * 用于获取链表的中间节点

     *

     * @return 链表的中间节点

     */

    public Node getMiddle(Node head) {

        if (head == null) {

            return null;

        }

        Node a = head, b = head;

        while (true) {

            if (b==null||b.next == null) {

                break;

            }

            b=b.next.next;

            a=a.next;

        }

        return a;

    }

    public static void main(String[] args){

        Node<String> a=new Node<String>("A");

        Node<String> b=new Node<String>("B");

        Node<String> c=new Node<String>("C");

        Node<String> d=new Node<String>("D");

        Node<String> e=new Node<String>("E");

        a.next=b;

        b.next=c;

        c.next=d;

        d.next=e;

        MiddleNode list=new MiddleNode();

        Node result=list.getMiddle(a);

        System.out.println(result.value);

    }

}

其中，测试用的链表如下：

A-->B-->C-->D-->E

回到目录|·(工)·）

巴特西

Q：链表的中间元素

问题：如何得到一个链表的中间元素？

最新文章

热门文章