题目：给定一个奇数个元素的链表，查找出这个链表中间位置的节点的数值。

示例：单链表：1 -> 2 -> 3 -> 4 -> 5 -> null，中间位置的节点的数值为3。

思路：由于单链表特性，我们只能先遍历一次才能得到其长度，得到总长度之后我们就知道其中间位置是第几个，再次进行遍历即可得到。这种暴力解法时间复杂度是：O(n) + O(2/n)。

下面介绍一种时间复杂度更低的解法：快慢指针法。

定义一快一慢两个指针：fast和slow，两个指针同时走，快指针每次走两步，慢指针每次走一步，当快指针走到链表末尾的时候，慢指针就恰好在链表中间位置，即我们需要的中间节点。

我们来看快慢指针的Java语言实现：

单链表节点类定义可查看文章：数据结构之链表-基础知识

1
2
3
4
5
6
7
8
9
public static SinglyLinkedListNode middleNode(SinglyLinkedListNode head) {
    SinglyLinkedListNode fast = head;
    SinglyLinkedListNode slow = head;
    while (fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}