再帰アルゴリズムにおけるリンクリスト操作

今日は、問題をさらに一歩進めて、再帰プロセスに対応する操作を追加する予定です。

(免責事項: 以下のソリューションは娯楽目的のみに提供されています。また、サンプル コードはコンパイルおよびデバッグされておらず、多くのアイデアは実際に検証されていません。)

リンク リスト内の N 番目から最後のノードを検索します。

解決策1

最後のノードまでレイヤーごとに再帰的にトラバースし、返されたノードから 1 回再帰的に逆方向に N 回トラバースして、N 番目から最後のノードを見つけます。

プライベートLNode targetNode = null ;
プライベートLNode FindLastNthNode(LNode ヘッド、 intインデックス)
 {
 (head.Next == null )の場合
    {
ヘッドを返す。
    } 
 
    最後のN番目のノードを検索します(head.Next、インデックス); 
 
    LNode tmpNode = ヘッド; 
 
 ((head.Next != null ) && (インデックス > 0))の間
    {
        ヘッド = head.Next;
        索引 - ;
    } 
 
 (head.Next == null && インデックス == 0)の場合
    {
        ターゲットノード = tmpNode;
 targetNodeを返します。
    } 
 
 targetNodeを返します。 
 
 }

分析する

1. 追加のグローバル ヘルパー変数。

2. 時間計算量は O(index * n) です。ここで、n はリンク リストの長さです。

3. パフォーマンスのオーバーヘッドは大きくなります。

解決策2（解決策1のバリエーション）

現在のノードが走査されるたびに、ループバックして n 個のノードを走査します。ノードが最後まで走査され、インデックスが 0 に減分された場合、現在のノードは最後に見つかった n 番目のノードであることを意味します。つまり、解決策 1 は後ろから前へ検索し、解決策 2 は前から後ろへ検索します。

プライベートLNode targetNode2 = null ; 
 
プライベートLNode FindLastNthNode2(LNode ヘッド、 intインデックス)
 {
 (head.Next == null )の場合
ヘッドを返す。 
 
    LNode tmpNode = ヘッド; 
 
 (head != null && index >= 0)の間
    {
        ヘッド = head.Next;
        索引 - ;
    } 
 
 if (head == null && index == 0)
    {
        ターゲットノード2 = tmpNode;
 targetNode2を返します。
    } 
 
 targetNode2を返します。
 }

分析: ソリューション 1 と同じです。

解決策3

プライベート 整数カウンター = 0;
プライベートLNode targetNode2; 
 
プライベートLNode FindLastNthNode2(LNode ヘッド、 intインデックス)
 {
 (head.Next == null )の場合
    {
        カウンター = インデックス;
ヘッドを返す。
    } 
 
    最後のN番目のノード2を検索します(head.Next、インデックス); 
 
    カウンタ - ; 
 
 （カウンタ == 0）の場合
    {
        ターゲットノード2 = ヘッド;
 targetNode2を返します。
    } 
 
 targetNode2を返します。
 }

【編集者のおすすめ】

1. さまざまな側面からみた Python コードのパフォーマンス最適化に関する新しい講演
2. 開発者のための時間管理のヒント
3. 開発者にとって最適なコード エディターは何ですか?
4. Web開発フレームワーク権限管理システム
5. インタビューコードの品質を向上させる3つの要素