找到中位数的节点

[1,2,3,4,5]

快慢指针法

找出链表中位数节点的方法多种多样，其中较为简单的一种是「快慢指针法」。初始时，快指针 fast 和慢指针 slow 均指向链表的左端点 left。我们将快指针 fast 向右移动两次的同时，将慢指针 slow 向右移动一次，直到快指针到达边界（即快指针到达右端点或快指针的下一个节点是右端点）。此时，慢指针对应的元素就是中位数。

代码实现

ListNode* getMedian(ListNode* left, ListNode* right) {
       ListNode* fast = left;
       ListNode* slow = left;
       while (fast != right && fast->next != right) {
           fast = fast->next;
           fast = fast->next;
           slow = slow->next;
       }
       return slow;
   }

方法 2

记录链表中节点的个数，然后除 2，再次遍历即可。