チェーンテーブルの中間ノード--速いポインタの思想

0x01.に質問
ヘッダノードheadを有する非空の単一チェーンテーブルが与えられ、チェーンテーブルの中間ノードが戻される.中間ノードが2つある場合は、2番目の中間ノードを返します.与えられたチェーンテーブルのノード数は、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.簡単な分析
単鎖表の問題、実は単鎖表がよく現れるのはこれらの問題だけで、どうしてですか?私たちをいじめているのは一方的で、後ろから前までそんなに便利ではないので、わざと位置を探す問題を整理しています.
何事も慌てないで、まず携帯電話を出して友达の輪を出して、自分で解決する方法があります.
一般的にこのような問題の解決方法は大きく3つに分けられます.

配列は、各ノードを格納する.

を複数回繰り返します.

クイックスローポインタ.

配列記憶は空間の消費を増大させ、何度も遍歴すると時間の消費を増大させるので、最良の状況は速遅指針法であり、この方法は単鎖表の魂と言えるが、多くの問題は巧みに解決することができる.
この問題では,速いポインタが2歩ずつ,遅いポインタが1歩ずつ歩くだけで,巧みに解決できる.
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