22-链表中间节点

自己的做法

算法思想

使用快慢指针。两个指针初始都指向头节点，快指针每次走两步，慢指针每次走一步。

当快指针到达链表末尾时，慢指针刚好指向中间节点。

该题说：如果有两个中间节点，返回第二个。

那么循环结束条件应该是：快指针的下一个节点为空，或快指针本身为空。

如果要返回第一个：那就是快指针的下一个节点或下下个节点为空。

算法实现

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode * fast = head;
        ListNode * slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。

官方做法

官方给了三个解法。

第一种使用数组，时间复杂度是$O(n)$，空间复杂度也是$O(n)$。

第二种是遍历两次链表，第一个获得链表长度，第二次根据链表长度找到中间节点。

第三种和我的做法一样。