单链表之查找单链表的中间节点

这个实际上之前在反转算法中已经实现过了，这里给大家复习以下思路。

思路

使用快指针和慢指针的方法，快指针每次走两步，慢指针每次走一步，当快指针到达尾部的时候，慢指针刚好走过了链表长度的1/2 即指向了中间节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 链表节点个数为奇数时返回中间节点
 * 为偶数时返回靠右的中间节点
 * @param head
 * @return
 */
public static ListNode findMiddleNode(ListNode head){
    if (head == null || head.next == null) {
        return head;
    }

    ListNode pSlow = head, pFast = head.next;
    while (pFast != null && pFast.next != null) {
        pFast = pFast.next.next;
        pSlow = pSlow.next;
    }

    // pFast == null时为链表个数奇数个，否则为偶数个（取决于快指针最开始从哪里起始）
    return pFast==null? pSlow:pSlow.next;
}

注意：这里会涉及到链表长度是偶数还是奇数的问题，可以看return语句中的三目运算，理解了之后就可以根据自己的需求灵活调整。