フロントエンドアルゴリズムシステム演習：リンクリストの章が完了

[[357916]]

実践する前に、データ構造やアルゴリズム、あるいはこのシリーズについての誤解を避けるために、まず私の観点を明確にしておきたいと思います。

皆さんの中には面接の準備をしている人もいると思いますので、面接はロケットを組み立てるようなもので、仕事はネジを締めるようなものだと聞いたことがあるはずです。多くの人がこの言葉を使って、大手インターネット企業のアルゴリズム面接を批判しています。そのため、次のような発言があります。面接に対処する以外に、アルゴリズムを学ぶことは実際には役に立たない。

私はこの意見に完全に反対しているわけではありません。なぜなら、テクノロジーエコシステムの発展により、この分野の最前線にいる専門家がすでに十分な車輪を準備しているからです。一般的なビジネス上の問題に遭遇したときは、彼らのソリューションをそのまま使用できます。さらに、最初は意味不明だと思った文章も目にしましたが、後で意味がわかりました。

習得するために一定の IQ 閾値を必要とするテクノロジーは、簡単に普及することはありません。

言い換えれば、テクノロジーがシンプルになればなるほど、人々はそれを積極的に使い、普及する可能性が高くなります。

これは、現在のさまざまな技術フレームワークを忠実に反映したものでもあります。つまり、使用するには十分であり、十分にシンプルで、基礎となるレイヤーの複雑な詳細を知る必要がないほどシンプルです。

そこで疑問なのが、知恵と才能を兼ね備えたプログラマーとしての私自身の価値は何なのか、ということです。

あなたの価値の大きさは、あなたが解決できる問題によって決まると思います。設計図に従って簡単なボタンを描くことができ、他のフロントエンド開発者も完成でき、バックエンドの学生でも同様の効果を達成できる場合、この時点でのあなたの個人的価値は何ですか？ほとんどの人が簡単にできることを、いつでも交代できるポジションで完成させただけです。張三が完成しても、李思が完成しても違いはありません。

しかし、今、複雑なエンジニアリングの問題に直面した場合、ビジネスを支援するためのスキャフォールディングツールを開発したり、プロジェクトのスケーラビリティを向上させるためにフレームワークのソースコードを修正したり、深刻なパフォーマンスの問題の原因を即座に分析して解決策を提示し、さまざまな要素のバランスをとったりする必要があります。これらは、アマチュアプレイヤーが短期間でできることではなく、ここにあなたの価値が反映されます。

アルゴリズム自体に戻ると、それはより複雑な問題を解決する能力の一部を表しています。したがって、長期的には、それは私たちの発展に微妙な助けとなるでしょう。次に、リンクリストの部分に進みます。主に以下のトピックに分かれています。

リンクリストを反転する

リンクリストを逆にする練習のための質問が 3 つあります。これらは、元の単一の連結リストの反転、2 つの連結リストの反転、K 個の連結リストの反転であり、段階的に難易度が増していきます。

面接で連結リストに遭遇すると、逆転の質問が最も頻繁に登場します。そのため、連結リストの入門トレーニングタイプと見なし、皆さんが十分に注意を払っていただければと思います💪。

NO.1 シンプルな逆リンクリスト

単一リンクリストを逆にします。

例：

入力: 1->2->3->4->5-> NULL  
出力: 5->4->3->2->1-> NULL  

出典: LeetCode 質問 206

循環型ソリューション

これは典型的なリンク リストの問題であり、リンク リスト データ構造は操作は簡単だが、実装はそれほど簡単ではないことを十分に示しています。

では、実装においてはどのような点に注意すべきでしょうか?

後続のノードを保存します。初心者の場合、現在のノードの次のポインターを前のノードに直接ポイントするのは簡単ですが、実際には現在のノードの次のノードのポインターは失われます。したがって、トラバーサル処理中は、まず次のノードを保存してから次のポイントを操作する必要があります。

リンクリスト構造は次のように定義されます。

関数ListNode(val) {
  this.val = val;
  this.next = null ;
 }

実装は次のとおりです。

 /**
 * @param {ListNode} ヘッド
 * @return {リストノード}
 */
逆リストを (head) => {
    もし (!head)
戻る ヌル;
    pre = null 、cur = head とします。
    （現在）{
        // キー: 次のノードの値を保存する
        next = cur.nextとします。
        cur.next = pre;
        前 = 現在;
        cur =次へ;
    }
戻り値:
 };

ロジックは比較的単純なので、コードは一度で完了できます。しかし、ただ書くだけでは十分ではありません。リンクリストの問題の場合、境界チェックの習慣はコードの品質をさらに保証するのに役立ちます。具体的には：

• ヘッドノードが空の場合は、✅で既に処理しています。
• リンクリストにノードが 1 つだけ含まれている場合は、このノードに直接戻りたいと考えます。上記のコードでは、ループに入った後、pre がヘッドである cur に割り当てられます。問題はありません。

LeetCode で実行し、AC に成功しました ✌

しかし、体系的なトレーニングとして、プログラムをそのまま通過させるのは性急すぎます。私たちは、将来同じ問題をさまざまな方法で解決して習得の効果を達成するために最善を尽くします。これは私たち自身の思考の拡張でもあり、時にはより良い解決策に到達するかもしれません。

再帰的解決

これまでのアイデアは非常に明確に紹介されているので、誰もが体験できるようにコードをここに貼り付けます。

逆リストを (head) => {
  逆順にする = (pre, cur) => {
    if(!cur) はpreを返します。
    //次のノードを保存する
    next = cur.nextとします。
    cur.next = pre;
逆順(cur, next )を返します。
  }
逆方向を返します( null 、 head )。
 }

No.2 レンジ反転

リンク リストを位置 m から n まで反転します。反転を完了するには、1 回のスキャンを使用してください。

注: 1 ≤ m ≤ n ≤ リンクリストの長さ。

例：

入力: 1->2->3->4->5-> NULL 、m = 2、n = 4
出力: 1->4->3->2->5-> NULL  

出典: LeetCode 問題 92

アイデア

リンクリスト全体を逆にする前の質問と比較すると、この質問は実際には本質的に同じです。ループソリューションと再帰ソリューションという 2 種類のソリューションがまだあります。

ここで注意が必要なのは、前のノードと次のノードの保存（または記録）です。これは何を意味するのでしょうか? この図を見ればわかります。

フロントノードとバックノードの定義については、図で明確に確認できるはずですし、後で頻繁に使用されます。

反転操作については前回の質問で分析済みですので、ここでは繰り返しません。注目すべきは、反転後の作業は実際には接ぎ木というプロセスであるということです。まず、前のノードの次のノードを間隔の終わりに向け、次に間隔の開始点の次のノードに向けます。したがって、この問題では、前のノード、次のノード、間隔の開始点、間隔の終了点の 4 つのノードに注意を払う必要があります。ここで実際のエンコード操作を開始します。

ループソリューション

/**
 * @param {ListNode} ヘッド
 * @param {数値} m
 * @param {数値} n
 * @return {リストノード}
 */
 var 逆方向Between =関数(head, m, n) {
    count = n - m とします。
    p = dummyHead = new ListNode() とします。
    let pre、cur、start、tail;
    先頭へ
(i = 0; i < m - 1; i++)の場合{
        p = p.next ;
    }
    // 前のノードを保存する
    前面 = p;
    // 区間の最初のノードを同時に保存する
    pre = tail = p.next ;
    cur = pre.next ;
    // 範囲の反転
( i = 0 とします; i < count ; i++) {
        next = cur.nextとします。
        cur.next = pre;
        pre = cur;
        cur =次へ;
    }
    // 前のノードの次のノードは間隔の終わりを指します
    front.next = 前;
    // 区間内の最初のノードの次のノードは次のノードを指します (ループが完了した後の cur は区間後の最初のノード、つまり次のノードです)
    tail.next = cur;
 dummyHead.nextを返します。
 };

再帰的解決

再帰ソリューションの場合、唯一の違いは区間の処理であり、これは再帰手順で実行されます。この機会に、再帰反転の実装を確認することもできます。

 var 逆方向Between =関数(head, m, n) {
  // 再帰逆関数
  逆順にする = (pre, cur) => {
    if(!cur) は preを返します。
    //次のノードを保存する
    next = cur.nextとします。
    cur.next = pre;
逆順(cur, next )を返します。
  }
  p = dummyHead = new ListNode() とします。
  ダミーヘッド.next =ヘッド;
  let start, end ; // 区間の最初と最後のノード
  let front, tail; // 前面ノードと背面ノード
( i = 0; i < m - 1; i++ とします) {
    p = p.next ;
  }
  front = p; //フロントノードを保存する
  開始 = front.next ;
 (i = m - 1; i < n; i++)の場合{
    p = p.next ;
  }
終了= p;
  tail = end . next ; //次のノードを保存する
終了。次へ= null ;
  // 針に糸を通し始めると、前のノードは間隔の始まりを指し、間隔の始まりは後ろのノードを指します
  front.next = 逆方向( null 、 start );
  start.next = 末尾;
 dummyHead.nextを返します。
 }

No.3 2つのグループでリンクリストを反転する

リンク リストが指定されると、隣接するノードをペアで交換し、交換されたリンク リストを返します。

ノード内の値を変更するだけでは不十分で、実際にノードを交換する必要があります。

出典: LeetCode 質問 24

例：

 1->2->3->4 の場合、2->1->4->3 を返す必要があります。

アイデア

図に示すように、まず分析を支援するためにダミー ヘッド ノード (dummyHead) を作成します。

まず、p を dummyHead の位置に置き、p.next と p.next.next のノード、つまり node1 と node2 を記録します。

次に、node1.next = node2.next とすると、効果は次のようになります。

次に、node2.next = node1 とすると、効果は次のようになります。

最後に、dummyHead.next = node2 となり、反転が完了します。同時に、p ポインターは node1 を指し、その効果は次のようになります。

このように、p.next または p.next.next が空の場合、つまり新しいノード セットが見つからない場合は、ループが終了します。

ループソリューション

アイデアは明確で、実際に実装するのは非常に簡単です。コードは次のとおりです。

 var swapPairs =関数(head) {
    head == null || head.next == nullの場合
ヘッドを返す。
    dummyHead = p = new ListNode() とします。
    ノード1、ノード2とします。
    ダミーヘッド.next =ヘッド;
    while((node1 = p.next ) && (node2 = p.next.next ) ) {
        ノード1の次=ノード2の次;
        ノード2の次= ノード1;
        ノード2をコピーします。
        ノード1
    }
 dummyHead.nextを返します。
 };

再帰法

var swapPairs =関数(head) {
    head == null || head.next == nullの場合
ヘッドを返す。
    node1 = head、node2 = head.nextとします。
    ノード1のnextをスワップペア(ノード2のnext )に変換します。
    ノード2の次= ノード1;
ノード2を返します。
 };

再帰を使用した後、コードが特に簡潔になったと感じますか?😃😃😃

再帰呼び出しのプロセスを完全に理解していただければ幸いです。これを理解することで、大きな進歩が得られると信じています。

No.4 逆リンクリストの K グループ

リンク リストが与えられると、グループ内の k 個のノードすべてが反転されます。反転されたリンク リストを返してください。

k は、リンク リストの長さ以下の正の整数です。

ノードの合計数が k の整数倍でない場合は、最後に残ったノードを元の順序のまま保持します。

例：

このリンクリストを考えると: 1->2->3->4->5
 k = 2 の場合、2->1->4->3->5 が返されます。
 k = 3 の場合、次の値が返されます: 3->2->1->4->5

例:

• アルゴリズムでは、一定の追加スペースのみを使用できます。
• ノード内の値を変更するだけでは不十分で、実際にノードを交換する必要があります。

出典: LeetCode 質問 25

アイデア

このアイデアは、No.3 の 2 つのグループを反転させるのと似ています。唯一の違いは、2 つのグループの場合は各グループで 2 つのノードのみを反転する必要があるのに対し、K のグループの場合は対応する操作は K 要素のリンク リストを反転することです。

再帰的解決

この問題については、再帰的な解決法の方が理解しやすいと思うので、まずは再帰的な方法のコードを貼り付けます。

• 次のコードのコメントでは、「最初のノード」や「最後のノード」などの概念は、反転前のリンク リストを指します。

 /**
 * @param {ListNode} ヘッド
 * @param {数値} k
 * @return {リストノード}
 */
 var 逆Kグループ =関数(head, k) {
    pre = null 、cur = head とします。
    p = head とします。
    // 次のループは、次の要素がグループを形成できるかどうかを確認するために使用されます
( i = 0; i < k; i++ とします) {
        if(p == null )はヘッドを返します。
        p = p.next ;
    }
 ( i = 0; i < k; i++ とします){
        next = cur.nextとします。
        cur.next = pre;
        pre = cur;
        cur =次へ;
    }
    // pre はこのグループの最後のノード、cur は次のグループの開始点です
    head.next = 逆Kグループ(cur、k);
戻り値:
 };

ループソリューション

コメントに重点が置かれています。

 var 逆Kグループ =関数(head, k) {
    count = 0 とします。
    // グループを形成できるかどうかを確認し、リンクリスト内の要素の数を数えます
(p = head とします; p != null ; p = p.next ) {
        if(p == null && i < k) はヘッドを返します。
カウント++;
    }
    loopCount = Math.floor( count / k )とします。
    p = dummyHead = new ListNode() とします。
    ダミーヘッド.next =ヘッド;
    // loopCount グループに分割し、各グループを反転します
( i = 0 とします; i < loopCount; i++) {
        pre = null 、cur = p.nextとします。
 (j = 0; j < k; j++)の場合{
            next = cur.nextとします。
            cur.next = pre;
            pre = cur;
            cur =次へ;
        }
        // 現在、pre はこのグループの末尾ノードであり、cur は次のグループの先頭ノードです
        let start = p.next ; // startはグループの最初のノードです
        // 針に糸を通し始めましょう!考え方は2人組の場合と全く同じである。
        p.next = 前;
        start.next = cur;
        p = 開始;
    }
 dummyHead.nextを返します。
 };

循環リンクリスト

NO.1 リンクリスト内のループを検出するにはどうすればいいですか?

リンク リストが与えられた場合、リンク リストにサイクルが形成されているかどうかを判断します。

アイデア

アイデア 1: ループを 1 回実行し、Set データ構造を使用してノードを保存し、ノードのメモリ アドレスを使用して重複を検出します。同じノードが 2 回アクセスされた場合、サイクルが形成されたことを意味します。

アイデア 2: 高速ポインタと低速ポインタを使用します。高速ポインタは一度に 2 ステップ進み、低速ポインタは一度に 1 ステップ進みます。2 つが出会うと、ループが形成されたことを意味します。

2 番目のアイデアの 2 つのポインタがリング内で必ず出会うのはなぜかと疑問に思うかもしれません。

実は、とても簡単です。リングがある場合、両方が同時にリングに入る必要があります。次に、リング内で、低速ポインターを参照システムとして選択します。高速ポインターが参照システムに対して1ステップ前進するたびに、最終的には原点に戻ります。つまり、低速ポインターの位置に戻り、2つが出会うことができます。指輪がなければ、二人の間の相対的な距離はどんどん大きくなり、二人は決して出会うことはないでしょう。

次に、プログラムで実装してみましょう。

方法1: 重量決定を設定する

/**
 * @param {ListNode} ヘッド
 * @return {ブール値}
 */
 var hasCycle = (head) => {
    set = new Set () とします。
    p = head とします。
    while(p) {
        // 同じノードが再び出現し、循環を示している
        if( set.has (p))戻り値 真実;
設定します。追加します(p);
        p = p.next ;
    }
戻る 間違い;
 }

方法2: 高速ポインターと低速ポインター

var hasCycle =関数(head) {
    dummyHead = new ListNode(); とします。
    ダミーヘッド.next =ヘッド;
    fast = slow = dummyHead とします。
    // ノードが 0 個または 1 個の場合、サイクルは発生しません
    fast.next == nullの場合|| fast.next.next == null )
戻る 間違い;
    while(fast && fast.next ) {
        高速= fast.next.next ;
        遅い = slow.next ;
        // 二人は出会った
        if(速い == 遅い) {
戻る 真実;
        }
    }
戻る 間違い;
 };

No.2 リングの始点の見つけ方

リンク リストが指定されている場合、リンク リストがループを開始する最初のノードを返します。 リンクリストにサイクルがない場合、null を返します。

**説明:** 指定されたリンク リストの変更は許可されていません。

思考分析

ループの存在を判断する方法はわかりましたが、ループのノードを見つけるにはどうすればよいでしょうか。分析してみましょう。

複雑そうに見えるので、さらに抽象化してみましょう。

高速ポインタと低速ポインタが x 秒間移動し、低速ポインタが 1 秒ごとに 1 回移動するとします。

高速ポインタの場合、次の式が成り立ちます: 2x - L = m * S + Y -----①

遅いポインタの場合、次の式が成り立ちます: x - L = n * S + Y -----②

このうち、m と n はともに自然数です。

① - ② * 2 は次のようになります。

L = (m - n) * S - Y-----③

はい、これは非常に重要な方程式です。ここで、セグメント L の左端に新しいポインタがあり、遅いポインタはまだ会合点にあると仮定します。

新しいポインタと遅いポインタを 1 ステップずつ進めます。次に、新しいポインタが L ステップ進むと、リングの開始点に到達します。同時に、遅いポインタに何が起こるかを見てみましょう。

式③から、スローポインタは（m - n）* S - Y単位移動したことがわかります。リングの始点を基準にすると、両者が出会う位置はYです。ここで、Y + (m - n) * S - Y、つまり（m - n）* Sから、スローポインタはリングの始点を基準に実際には（m - n）円移動したことがわかります。つまり、この時点でスローポインタもリングの始点に到達していることになります。 :::tip 結論 これで解決方法は非常に明確になりました。高速ポインタと低速ポインタが出会ったら、新しいポインタを最初から開始し、低速ポインタと同時に前進させ、毎回 1 ステップずつ前進させます。2 つが出会った場所がループの開始点です。 :::

プログラミング実装

原理を理解すれば、実装がはるかに簡単になります。

 /**
 * @param {ListNode} ヘッド
 * @return {リストノード}
 */
 var 検出サイクル =関数(ヘッド) {
    dummyHead = new ListNode(); とします。
    ダミーヘッド.next =ヘッド;
    fast = slow = dummyHead とします。
    // ノードが 0 個または 1 個の場合、サイクルは発生しません
    fast.next == nullの場合|| fast.next.next == null )
戻る ヌル;
    while(fast && fast.next ) {
        高速= fast.next.next ;
        遅い = slow.next ;
        // 二人は出会った
        if(速い == 遅い) {
           p = dummyHead とします。
           while(p != slow) {
               p = p.next ;
               遅い = slow.next ;
           }
 pを返します。
        }
    }
戻る ヌル;
 };

リンクリストのマージ

NO.1 2つの順序付きリンクリストを結合する

2 つのソートされたリンク リストを新しいソートされたリンク リストにマージして返します。新しいリンク リストは、指定された 2 つのリンク リストのすべてのノードを連結することによって構築されます。

例：

入力: 1->2->4、1->3->4
出力: 1->1->2->3->4->4

出典: LeetCode 質問 21

再帰的解決

再帰的なソリューションの方が理解しやすいので、まずは再帰的に実行してみましょう。

 /**
 * @param {リストノード} l1
 * @param {リストノード} l2
 * @return {リストノード}
 */
 var mergeTwoLists =関数(l1, l2) {
    定数マージ = (l1, l2) => {
        l1 == nullの場合、 l2を返します。
        l2 == nullの場合、 l1を返します。
        l1.val > l2.val の場合 {
            l2.next = merge(l1, l2.next ) ;
 l2を返します。
        }それ以外{
            l1.next = merge(l1.next , l2);
 l1を返します。
        }
    }
マージ(l1, l2)を返します。
 };

ループソリューション

var mergeTwoLists =関数(l1, l2) {
    l1 == nullの場合、 l2を返します。
    l2 == nullの場合、 l1を返します。
    p = dummyHead = new ListNode() とします。
    p1 = l1、p2 = l2とします。
    p1とp2の間{
        p1.val > p2.valの場合{
            p.next = p2;
            p = p.next ;
            p2 = p2.next ;
        }それ以外{
            p1を次に示します。
            p = p.next ;
            p1 = p1.next ;
        }
    }
    // ループが完了したら必ず残りをチェックしてください
    p1の場合、 p.next = p1;
そうでない場合、 p.next = p2 ;
 dummyHead.nextを返します。
 };

No.2 K 順序付きリンクリストをマージする

k 個のソートされたリンク リストをマージし、マージされたソートされたリンク リストを返します。アルゴリズムの複雑さを分析して説明してください。

例：

入力：
 [
  1->4->5、
  1->3->4、
  2->6
 ]
出力: 1->1->2->3->4->4->5->6

出典: LeetCode 質問 23

トップダウン（再帰的）実装

/**
 * @param {ListNode[]} リスト
 * @return {リストノード}
 */
 var mergeKLists =関数(リスト) {
    // 上記ですでに実装済み
    var mergeTwoLists = function (l1, l2){/*上記ですでに実装済み*/;
    const _mergeLists = (リスト、開始、終了) => {
        if(終了- 開始 < 0)戻り値 ヌル;
        if( end - start == 0)リスト[ end ]を返します。
        mid = Math.floor(start + ( end - start) / 2);とします。
 mergeTwoList を返します(_mergeLists(lists, start, mid), _mergeLists(lists, mid + 1, end ));
    }
 _mergeLists(リスト、0、リストの長さ - 1)を返します。
 };

ボトムアップ実装

ここで思い出していただきたいのは、ボトムアップ実装では、各リンク リストに dummyHead ポインターをバインドするということです。なぜこれを行うのでしょうか。

これは、リンク リストのマージを容易にするためです。たとえば、l1 と l2 がマージされた後、マージされたリンク リストのヘッド ポインターは l1 の dummyHead.next 値に直接なります。つまり、両方のリンク リストが l1 にマージされ、後続のマージ操作が容易になります。

 var mergeKLists =関数(リスト) {
    var mergeTwoLists = function (l1, l2){/*上記ですでに実装済み*/;
    // エッジケース
    if (!リスト || !リスト.長さ)戻り値 ヌル;
    // 仮想ヘッドポインタコレクション
    dummyHeads = [] とします。
    // 仮想ヘッドポインタを初期化する
( i = 0 とします; i < lists.length; i++) {
        ノードを新しいListNode()にします。
        ノードの次のリスト[i];
        dummyHeads[i] = ノード;
    }
    // 下から上にマージ
(let size = 1 ; size < lists.length; size += size ) {
 ( i = 0 とします; i + size < lists.length; i += 2 * size ) {
            dummyHeads[i] .next = mergeTwoLists(dummyHeads[i] .next , dummyHeads[i + size ] .next );
        }
    }
 dummyHeads[0] .nextを返します。
 };

これで複数の連結リストのマージが完了しました。ちなみに、このマージ方法は連結リストのマージとソートのコアコードでもあります。トップダウンとボトムアップのアプローチの異なる実装の詳細を理解していただければ幸いです。プログラミング スキルの向上につながると思います。

リンクリストの中間ノードを見つける

回文リストを決定する

単一リンクリストが回文であるかどうかを判断してください。

例1:

入力: 1->2
出力: false  

例2:

入力: 1->2->2->1
出力: true  

この問題を O(n) 時間と O(1) の空間で解くことができますか?

出典: LeetCode 質問 234

思考分析

パフォーマンスの制限を考慮しなければ、この問題は実際には非常に単純です。しかし、O(n) の時間計算量と O(1) の空間計算量を考慮すると、立ち止まって考える価値はあるでしょう。

この問題では単一のリンク リストが必要であり、前のノードにアクセスする方法がないため、別の方法を見つける必要があります。

リンクされたリストの中間点を見つけ、後半部分を逆にすると、それらを 1 つずつ比較して結論を​​導き出すことができます。これを実装してみましょう。

コードの実装

実際、コードの重要な部分は中間点を見つけることです。まず剣を抜きます。

 dummyHead を slow と fast に置き換えて、新しい ListNode() を作成します。
ダミーヘッド.next =ヘッド;
 // 注意してください、中間点が来ます
while(fast && fast.next ) {
    遅い = slow.next ;
    高速= fast.next.next ;
 }

なぜこのように境界が設定されているのだろうかと疑問に思うかもしれません。

リンクリスト内のノード数が奇数の場合と偶数の場合を別々に分析して説明しましょう。

リンクリストのノード数が奇数の場合

シミュレーションしてみてください。fast が空になったらループを停止し、ステータスは次のようになります。

リンクリストのノード数が偶数の場合

シミュレーションは 1 回実行されます。fast.next が空の場合、ループは停止し、ステータスは次のようになります。

fast が空であることと fast.next が空であることの 2 つの条件では、奇数の場合は fast が常に空であることが最初に表示され、偶数の場合は fast.next が常に最初に表示されます。

つまり、 fast が空になると、リンク リスト ノードの数は奇数になる必要があり、そうでない場合は偶数になります。したがって、2 つのケースを一緒に議論することができます。 fast が空の場合、または fast.next が空の場合、ループは終了できます。

完全な実装は次のとおりです。

 /**
 * @param {ListNode} ヘッド
 * @return {ブール値}
 */
 var isPalindrome =関数(head) {
    逆順にする = (pre, cur) => {
        if(!cur) はpreを返します。
        next = cur.nextとします。
        cur.next = pre;
逆順(cur, next )を返します。
    }
    dummyHead を slow と fast に置き換えて、新しい ListNode() を作成します。
    ダミーヘッド.next =ヘッド;
    // 注意してください、中間点、黄金のテンプレートがここにあります
    while(fast && fast.next ) {
        遅い = slow.next ;
        高速= fast.next.next ;
    }
    next = slow.nextとします。
    slow.next = null ;
    newStart = river( null , next ) とします。
 ( p = head、 newP = newStart、 newP != null 、 p = p.next 、 newP = newP.next ) {
        if(p.val != newP.val)戻り値 間違い;
    }
戻る 真実;
 };