美文网首页
java算法:找到单链表的中间节点

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

作者: Bfmall | 来源:发表于2022-01-21 18:04 被阅读0次

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

    /**
         * 算法:找到单链表的中间节点
         * 通过快慢指针,快指针每次跳两个节点,慢指针每次跳一个节点,当快指针移动到末尾时,慢指针整好指向链表的中间节点。
         *           [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;
        }
    

    相关文章

      网友评论

          本文标题:java算法:找到单链表的中间节点

          本文链接:https://www.haomeiwen.com/subject/uvzehrtx.html