[数据结构与算法]力扣_876. 链表的中间结点

力扣

题目描述中有这个链表是非空单链表，它的长度不是奇数就是偶数，然后我们要找到它的中间结点，所以要分两种情况。

?1.在奇数的情况下，剩下要走的步数是偶数，因为fast和slow的起点位置是head
2.slow走1步，fast走2步
3.slow要走到中间时，要花费L/2步，而fast是slow的两倍，则slow走到中间时，正好走到末尾

?1.偶数时，剩下的步数走奇数步。

2.fast走两步，slow走一步，所以要想fast走到尾，必须要走出去。

3.slow走到中间的第二个需要走L/2步，fast要走L步，L是偶数，但剩下的是奇数，所以就走出去了。

?所以现在有两种情况，一是fast走到尾，二是fast走到NULL。?

这个方法叫：快慢指针法。

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head, *slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

?这个while循环的表达式，我们想的是while循环结束的条件，但是while表达式写的是继续的条件。

只要fast不为空并且fast->next不为空就继续迭代。

时间复杂度：O(N)，N为给定链表的结点数目。

空间复杂度：O(1)?，只需要常数（不变的数）的空间存放slow和fast两个指针。