链表的中间结点--快慢指针思想

0x01.问题

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
给定链表的结点数介于 1 和 100 之间。

C++结构体说明：
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 C++函数形式： ListNode* middleNode(ListNode* head)
 

0x02.简要分析

单链表问题，其实单链表经常出现的就这些问题，为什么？因为它欺负咱是单向的，从后到前没那么方便，所以故意整这些找位置的题。

凡事不要慌，先拿出手机发个朋友圈 ，自有解决的办法解决。

一般这类问题的解决方式大概分为三种：

• 数组存储每个结点。
• 多次遍历。
• 快慢指针。

数组存储会加大空间的消耗，多次遍历会加大时间的消耗，所以，最佳情况就是快慢指针法，这个方法可以说是单链表的灵魂，很多问题可以巧妙解决。

在这个问题中，只需要快指针每次走两步，慢指针每次走一步，就能巧妙解决。

0x03.解决代码–快慢指针

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

ATFWUS --Writing By 2020–03–23