java算法:找到单链表的中间节点

2022-01-21  本文已影响0人  Bfmall

实现思路:
通过快慢指针,快指针每次跳两个节点,慢指针每次跳一个节点,当快指针移动到末尾时,慢指针整好指向链表的中间节点。

/**
     * 算法:找到单链表的中间节点
     * 通过快慢指针,快指针每次跳两个节点,慢指针每次跳一个节点,当快指针移动到末尾时,慢指针整好指向链表的中间节点。
     *           [A]  ->  [B]  ->  [C]  ->  [D]  ->  [E]  ->  [F]
     *
     *  初始指针  f0
     *           s0
     *  第一次             s1       f1
     *  第二次                      s2                f2
     *  第三次                               s3                        f3 (已经遍历完毕链表,越界)
     * @param node
     * @return
     */
    public Node getMiddleNode(Node node) {
        if (node == null) {
            return null;
        }
        Node fastNode = node;
        Node slowNode = node;
        while (fastNode != null && fastNode.next != null && slowNode != null) {
            fastNode = fastNode.next.next;//跳两步
            slowNode = slowNode.next;//跳一步
        }
        return slowNode;
    }
上一篇下一篇

猜你喜欢

热点阅读