アルゴリズムの再帰(3)-チェーンテーブル操作

アルゴリズムの再帰(3)-チェーンテーブル操作
再帰(2)単一チェーンテーブルの遍歴を試み,再帰呼び出しの前か,再帰呼び出しの後か,独自の操作を追加する方法を解析した.
今日、再帰の過程で対応する操作を追加する問題を深く掘り下げるつもりです.
(免責声明:次の解法は娯楽にすぎません.また、サンプルコードはコンパイルされず、デバッグされず、多くのアイデアが実証されていません.)
チェーンテーブルの最後からN番目のノードを検索します.
解法一
層ごとに再帰し、最後のノードに遍歴し、戻ったノードから一度後ろに再帰し、N回遍歴し、最後からN番目のノードを見つけます.

        private LNode targetNode = null;



        private LNode FindLastNthNode(LNode head, int index)

        {

            if (head.Next == null)

            {

                return head;

            }



            FindLastNthNode(head.Next, index);



            LNode tmpNode = head;



            while ((head.Next != null) && (index > 0))

            {

                head = head.Next;

                index--;

            }



            if (head.Next == null && index == 0)

            {

                targetNode = tmpNode;

                return targetNode;

            }



            return targetNode;



        }

 
ぶんせき
1.追加のグローバル補助変数.
2.時間複雑度O(index*n)、nはチェーンテーブルの長さである.
3.パフォーマンスのオーバーヘッドが大きい.
かいほうにじゅう
現在のノードに巡回するたびに、すなわち再循環してn個を後方に巡回し、ノードが最後に巡回し、indexが0に自減すると、現在のノードが検索する逆数のn個目であることを示す.つまり、解法は1つは後ろから前へ、2つは前から後ろへ.

        private LNode targetNode2 = null;



        private LNode FindLastNthNode2(LNode head, int index)

        {

            if (head.Next == null)

                return head;



            LNode tmpNode = head;



            while (head != null && index >= 0)

            {

                head = head.Next;

                index--;

            }



            if (head == null && index == 0)

            {

                targetNode2 = tmpNode;

                return targetNode2;

            }



            return targetNode2;

        }

 
分析:解法と同じ.
解法三
最後のノードから再帰的に戻るとカウンタが減算され、0に等しい場合、このノードは検索する最後からN番目のノードであるグローバル変数を定義します.

        private int counter = 0;

        private LNode targetNode2;



        private LNode FindLastNthNode2(LNode head, int index)

        {

            if (head.Next == null)

            {

                counter = index;

                return head;

            }



            FindLastNthNode2(head.Next, index);



            counter--;



            if (counter == 0)

            {

                targetNode2 = head;

                return targetNode2;

            }



            return targetNode2;

        }

 
ぶんせき
1.2つの補助変数.
2.時間的複雑度はO(n)である.
3.余計なindex、厄介なcounter.
 
=======後記=======
実は以上のいくつかのソリューションは個人的にperfectが足りないと思います.
チェーンテーブルのような操作は、基本的に2つのポインタです.
そこで私は再び次のような案をあげました.
(このセグメントコードはコンパイル、実行、テストに合格しました)
 
解法四:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;



namespace ConsoleApplication17

{

    class Program

    {

        static void Main(string[] args)

        {

            Node head = new Node()

            {

                Data = "Head"

            };



            Node lucas = new Node()

            {

                Data = "Lucas"

            };



            Node bill = new Node()

            {

                Data = "Bill"

            };



            Node steve = new Node()

            {

                Data = "Steve"

            };



            Node anders = new Node()

            {

                Data = "Anders"

            };



            Node jordan = new Node()

            {

                Data = "Jordan"

            };



            head.Next = lucas;

            lucas.Next = bill;

            bill.Next = steve;

            steve.Next = anders;

            anders.Next = jordan;



            Program p = new Program();

            Node resultNode = p.FindLastNthNode(head, 2);



            Console.WriteLine(resultNode.Data);

            Console.ReadLine();

        }



        private Node FindLastNthNode(Node node, int n)

        {

            if(node == null)

            {

                return node;

            }



            if(n <= 0)

            {

                throw new ArgumentException("n");

            }



            Node node1 = node;

            Node node2 = node;



            return this.InternalFindLastNthNode(node1, node2, n);

        }



        private Node InternalFindLastNthNode(Node node1, Node node2, int n)

        {

            if(node1 == null)

            {

                return node2;

            }



            if(n == 0)

            {

                return this.InternalFindLastNthNode(node1.Next, node2.Next, 0);

            }



            return this.InternalFindLastNthNode(node1.Next, node2, --n);

        }

    }



    public class Node

    {

        public string Data { get; set; }

        public Node Next { get; set; }

    }

}

 
 
Best Regards,
Lucas Luo