给定一个头结点为 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
思路: 快慢指针法,慢的走一步,快的走两步,快的走到头时,慢的正好走到中间位置。
该思路,同环形链表一样。
ListNode* middleNode(ListNode* head) {
if (!head || !head->next)
return head;
ListNode *slow = head;
ListNode *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}