LeetCodeの問題解決：206.reverseList、JavaScript、詳細なメモを使ったわかりやすい再帰の説明

元の質問へのリンク

1->2->3->4->5->NULL連鎖したテーブルがあると仮定すると、再帰のステップは以下のようになります：

1. 再帰が最も深い点に達すると、その時点でreverseList(5)が実行され、5が返されます。
2. reverseList(5) の最上位は reverseList(4) で、この時点では以下のように実行されます：
   • headNextは実際には5で、この時点では連鎖表は `1->2->3->4->5->NULL`` のままです。
   • head.next.next = head;を1->2->3->4<=>5実行すると、実際には5のポインティングが4に変更され、チェインテーブルは4と5が互いにポインティングされた , になります。
   • 1->2->3->4<-5head.next=null;を実行すると、チェーンテーブルは+4->NULLとなり、4は3と5によって同時にポイントされ、4はnullを隠しポイントしていることに注意してください。
   • 上記の書き方は理解を助けるためのもので、実際には連鎖表は2つのセグメントに分割されており、それぞれ1->2->3->4とNULL<-4<-5となっています。
   • 最後に、reverseList(4) の戻り値は、実際には 5->4 です。
3. reverseList(4) の最上位は reverseList(3) で、この時点では以下のように実行されます：
   • 1->2->3->4<-5headNext は実際には 5->4 であり、この時点でのチェーンテーブルは +4->NULL です。
   • head.next.next = head;を1->2->3<=>4<->5実行すると、3と4のポインティングが反転し、この時点ではまだ5->4がポインティングされています。
   • 1->2->3<-4<-5head.next = null;を実行すると、連鎖表は+3->NULLとなり、このとき、3は2と4から同時に指され、3はNULLを指していることが隠されていることに注意する必要があります。
   • 上記の書き方は理解を助けるためのもので、実際には連鎖表は2つのセクションに分割されており、それぞれ1->2->3とNULL<-3<-4<-5となっています。
   • reverseList(3) の最終的な戻り値は、実際には 5->4->3 です。
4. NULL<-1<-2<-3<-4<-5その後の再帰は、上記のステップを繰り返し、最終的な結果は.

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
 // ノードが空であったり、ノードが1つしかなかったりする場合は避けること
 if (head === null || head.next === null) {
 return head;
 }
 // headヘッド内の以下のコメントに注意してほしい。.prev、head.nextすべて元の配列のノードを指す
 // reverseList返されるノードは、実際には元のリストの最後のノードであり、新しいリストの最初のノードである。
 const headNext = reverseList(head.next);
 // のヘッダを置く。.nextを指す2つの反転を完了し、HEADを指す。
 // しかし、この時点でポインタは実際にはheadになる。.prev -> head <=> head.next
 // つまり、headとhead.next互いを指す
 head.next.next = head;
 // を指すヘッドを空にする。
 head.next = null;
 // 先頭に.next上位呼び出しに戻る
 return headNext;
};