逆連結リスト

これが人気のインタビュー質問であるので、reversing a singly linked listをしましょう!

The problem is, given the head of a singly linked list, reverse it, and return the reversed list.

我々は、新しい問題を作成する代わりに、元のリストを並べ替えることによって、この問題を解決することができますし、テールノードをリストの新しい頭として返す.
我々が最初のノードを見るならば、我々はそれについて何を知っていますか?私たちは、それが次のノードへのポインタを持っていることを知っています.すぐに次のポインタをすぐに逆にすると、リストの残りの部分を疎遠にします.また、どのノードを指しているかを知りません.我々は、ノードを追跡するいくつかのヘルパーカーソルが必要です!
このように、currは現在のノードを覚えている3つのカーソルを定義し、前のノード(最初にNULLに初期化)を覚えておく前に、次のノードを覚えておくためにTMPを定義します(ループ内のローカル変数として定義します).

const reverseList = (head) => {
  let curr = head; //cursor to the current node
  let prev = null; //cursor to the previous node
...
}

次のノードを覚えているので、カーソルを安全に変更できます.しかし、順序は重要です!
まず、currポインタを後方に移動して前のノードとリンクします(最初はNULL ).

curr.next = prev;

そしてprevが現在のノードになり、次のノードになります.

prev = curr;
curr = tmp;

それは、次の繰り返しでは、次のノードに移動し、プロセスを繰り返すことができます.

最後に到達しない限り、リストに沿って移動します.サイクルの最後までに、リストの新しい先頭を返します.prevノードはprevノードです( prev . nextはnext . nextからNULLです).

while (curr) { //curr !== null
    let tmp = curr.next; //move cursor to the next node

    curr.next = prev; //1.change curr pointer backwards
    prev = curr; //2.change prev cursor to current
    curr = tmp; //3.move cur cursor to the next node
  }

一緒に置きましょう.

const reverseList = (head) => {
  let curr = head; //cursor to the current node
  let prev = null; //cursor to the previous node

  while (curr) { //curr !== null
    let tmp = curr.next; //move cursor to the next node

    curr.next = prev; //1.change curr pointer backwards
    prev = curr; //2.change prev cursor to current
    curr = tmp; //3.move cur cursor to the next node
  }
  return prev; //return a new head of the list
};

我々はより良い再帰でそれを行うことができます!ノウハウ?コメントであなたのソリューションを共有すること自由に感じなさい!