Letcode 25k群の逆節点

leetcode 25の解法k群の逆節点Click hereあなた自身を試してみてください!

leetcode問題文

リンクリストの先頭を指定し、リストkのノードを一度に反転し、変更リストを返します.
Kは正の整数であり、リンクリストの長さ以下である.ノードの数がkの倍数でないならば、出てきたノードは最後に、それのままであるべきです.
リストのノードの値を変更することはできません.
例:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

初期思考

私にとって、これらの問題は概念的に理解しやすい.ここでの挑戦的な部分は、実装を考え出すことです.リンクリストの問題では、ポインタを追跡するキーです.

破壊する

例を見て、実装がどのように見えるかを理解するために、それを通して働き始めます.

概要

これを見ると、ノードをカウントする方法が必要です.kノードに到達したら、いくつかの操作を実行しなければなりません.一度それを行うと、次のkノードに移動できます.

kノードに到達したらどうするか

KTHノードに到達したら、リストを1から2に戻す必要があります.リストを逆にするには、startingNodeが必要になります.これを追跡するポインタが必要になります.

その後、リストを切断することができますし、再接続する権利を追跡する.

サブリストの反転

今、我々は実際にリストを逆にすることができます.我々は、ここでLinkedlist逆転に関して深いダイビングをしていません.LinkedListを逆にする方法に精通していないならば、私はあなたがこの問題に飛び込む前に最初に学ぶことを強く勧めます.
一度リストを返します.

Important observation here. Notice how starting node is now the tail of our subList, and currentNode is the head.

逆のサブリストをメインリストに再接続し、次の反復の再設定

再接続してリセットするには、以下の操作をポインタで実行します.

startingNode.next = rightPart
startingNode = rightPart
currentNode = rightPart
counter = 1

結果:

Hmm ok, we have made some progress. There are two things that we are missing here though…

leftpartについては?

leftpartがまだ動いているのを見ていません、しかし、あなたが多分推測したように、我々はこれを扱わなければなりません.これを扱うにはleftpartポインタを使います.

我々がやってしまえば、我々は何を返すだろうか?

最初のサブリストのNeWHEADを返さなければなりません.これを処理するには、あなたが推測できます.

逆のサブリストをメインリストに再接続し、leftpartとnewheadで次の反復処理を再設定する

次に、次の操作を実行します.

startingNode.next = rightPart // connect the list
newHead = currentNode // set the newHead, we will only do this once
leftPart = startingNode // save the leftPart for the next iteration
startingNode = rightPart // save the next startingNode
currentNode = rightPart // set up the next currentNode
counter = 1 // reset the counter

それから、我々は残っています...

リストの真ん中の次の反復の主なリストと再設定に逆のサブリストを再接続する

サブリストを切断して実行します.

rightPart = currentNode.next // save the rightPart
currentNode.next = null, disconnect from the main list
reverse(startingNode) // reverse the subList

…に終わる.

サブリストをメインリストに再接続し、次の反復処理をリセットします.

leftPart.next = currentNode // connect the leftPart
startingNode.next = rightPart // connect the rightPart
leftPart = startingNode // set the next leftPart
startingNode = rightPart // set the next startingNode
currentNode = rightPart // set the next currentNode
counter = 1 // reset the counter

…に終わる.

ニース、我々のプロセスはすべての中間のサブリストを扱うべきです.

リストの最後の取り扱い

ここでは、我々の現在の流れによるKに等しいカウンタ2は、我々のサブリスト反転を引き起こします、しかし、これが長さ2で本当のサブリストでないので、それはそうしてはいけません.この場合を処理するには、

if (currentNode !== null && counter === k)

これを加えて、我々は望ましいふるまいを得ます.いいね

アルゴリズム計画

エッジケース処理

K = = 1の場合、ヘッドを返します.(この場合は何も処理する必要はありません.
グローバル変数

宣言されたleftpartはNULL

に初期化される

宣言は、ヌル

に初期化します

宣言は、ヘッド562479182に初期化する

宣言startingnodeは、ヘッド562479182に初期化する

DECLAREカウンタ初期化
メインループ

CurrentNodeを使用してリストを繰り返しますNULL

は、各々の反復

のカウンタを増やす

カウンタ== kとcurrentNode = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =NULL

RightPartを宣言し、CurrentNodeに初期化します.次の繰り返しのための次の

は切断して、

を逆にします

CurrentNodeを設定します.NULLの隣にリスト

を切断します

はStartingNode

からリストを反転させる

頭がない場合、CurrentNode

に設定します

再接続

左に接続します.leftpartがあれば、currentnode

に接続します

右側に接続します.Rightpart

の隣に
次の繰返しのために再設定される

LeftPartにノード

を設定する

RightPartノードをRightPart

に設定する

RightPart

にCurrentNodeを設定する

は1

にカウンタをセットしました

は、NEWHEAD

を返します
コードをアップしましょう!

コード

const reverseKGroup = (head, k) => {

    // Handle edge case
    if (k === 1) {
        return head;
    }

    let leftPart = null;
    let newHead = null;
    let currentNode = head;
    let startingNode = head;
    let counter = 1;

    while (currentNode) {
        currentNode = currentNode.next;
        counter++;
        if (currentNode && counter === k) {

            // Save right part for next iteration    
            let rightPart = currentNode.next;

            // Disconnect and reverse
            currentNode.next = null;
            reverse(startingNode);

            // Set newHead if needed
            if (newHead === null) {
                newHead = currentNode;
            }

            // Connect the list back
            if (leftPart !== null) {
                leftPart.next = currentNode;
            } 
            startingNode.next = rightPart;

            // Reset for the next iteration
            leftPart = startingNode;
            startingNode = rightPart;
            currentNode = rightPart;
            counter = 1;
        }
    }

    return newHead;
}

const reverse = (node) => {
    let prev = null;
    let currentNode = node;
    while (currentNode) {
        let nextNode = currentNode.next;
        currentNode.next = prev;
        prev = currentNode;
        currentNode = nextNode;
    }
    return prev; // returning for as a good practice, not needed in this problem
}

概要

このアルゴリズムはo(n)時間で実行され,nはリストのノード数,o(1)空間である.
ご覧の通り、コードはかなり些細です.それは非常に簡単に追跡する必要があるすべての別のポインタをトリミング取得することです.私は確かに!

Having a good mental model is key, and drawing things out really helps especially if your more visually inclined. In fact, I’d say that’s probably true for most problems.

これが役に立つという望み!