LeetCode第 876 题：链表的中间结点(C++)

leetcode链接

快慢指针

已经很熟练了，注意返回值判断即可

class Solution { public: ListNode* middleNode(ListNode* head) { // 只有一个结点 if(head->next == NULL){ return head; } auto slow_p = head; auto fast_p = slow_p; while(true){ if(fast_p->next == NULL){ return slow_p; }else if(fast_p->next->next == NULL){ return slow_p->next; }else{ slow_p = slow_p->next; fast_p = fast_p->next->next; } } } };

优化一下：

class Solution { public: ListNode* middleNode(ListNode* head) { ListNode* slow_p = head; ListNode* fast_p = head; while (fast_p != NULL && fast_p->next != NULL) { slow_p = slow_p->next; fast_p = fast_p->next->next; } return slow_p; } };

单指针

我们可以对链表进行两次遍历： 第一次：统计元素个数 N； 第二次：遍历到第 N/2 个元素，将其返回。

其他容器

链表即便知道长度，要获取中间结点依然需要遍历，但是数组或者vector等可以进行下标访问直接返回中间结点，所以一次遍历将结点（是结点，不是结点存储的数据）全部存入容器，遍历完成直接从容器中获取结点即可。