LeetCodeのJavaScript解答第206題——リバースチェーン(Reverse Liked List)

Time:2019/4/23 Title:Reverse Linked Difficulty:Easy Author:小鹿
タイトル:Reverse Linked List(逆転チェーン)
Reverse a singly linked list.
Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:
A linked list can be reversed either iterabiely or recursively.Could you implement both?
Solve:
π問題分析
1)チェーンを反転させる私たちが最初に考えられる方法は、最もよく使われている方法であり、三つのポインタを声明して、頭の結点が最後の結点になり、次の結点が最後の結点の頭につながって、類推することである.つまり、直接チェーンゲージを反転させることによって、逆チェーンが実現されます.
πアルゴリズムの考え方
二つの方法:

一般反転

再帰法

一般的な解決:
1)3つのポインタを定義し、それぞれPnext、pre、currentとして現在のノードを記憶し、preは反転した結点の先頭結点を指し、Pnextは次の結点情報を記憶する.
2)現在の結点が反転できるかどうかを判断します.
ステップ:
1)Pnextポインタは次のノードを記憶します.
2)現在の結点のnext結点はnullかどうか(nullであれば現在の結点は最後の結点)、nullであれば、現在のノードにheadヘッドポインタ(破断箇所)を割り当てます.
3)preポインタが指す結点は、現在のノードcurrentの次の結点nextに値します.
4)preポインタを現在のノードcurrentに向ける.
5)currentは引き続き巡回し、現在ノードはcurrentをPnextに指す.
再帰法(重点分析):
1)まず終了条件を決定します.次のノードがnullの場合、現在のノードに戻ります.
2)現在のチェーンがnullかどうかを判断する.
3)再帰的に末尾の結点を見つけて、頭の結点として保存します.
4)この時点で再帰的な階層は第二層再帰的であるので、先頭ノードに設定する次の結点は現在の第二層の結点であり、第二ノードの次の結点はbullに設定される.
π試験用例
1)チェーンは空チェーンです.
2)現在のチェーンの長さは1以下です.
3)入力長さが1より大きいチェーンテーブル.
π再帰法

const reverseList = (head)=>{
       if(head == null || head.next == null){
           return head;
       }else{
           let newhead = reverseList(head.next);
           head.next.next = head;
           head.next = null;
           return newhead;
       }
   }

π性能分析

時間の複雑さ:O(n).チェーン全体を経るだけで反転ができます.時間の複雑さはO(n)です.

空間複雑度:O(1).定数レベルの空間だけが必要で、空間の複雑さはO(1)です.

LeetCodeオープンソースGithub倉庫に一緒に参加することを歓迎します.他の言語のコードを私に提出してもいいです.倉庫の上で堅持して子供達と一緒にカードを打って、共に私達の開源小倉庫を改善します!
Github:https://github.com/luxiangqiang/JS-LeetCode
私の個人番号に注目してください.「平凡に甘んじない私たち」は自分でプログラミングした物語を記録しました.