题目描述

找出非空单链表的中间结点，如果有两个中间结点（链表结点数为偶数），返回第二个中间结点。

样例

输入: [1,2,3,4,5]
输出：结点3

算法

(快慢指针) $O(n)$

快指针每次走两步，慢指针每次走一步，当快指针无法移动时，慢指针则到达中间结点，返回即可。

时间复杂度分析：需要遍历链表，复杂度为$O(n)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};