c# - 単一リンクリストを逆方向に読む方法は?

Question

私が考えることができる 1 つの方法は、リストを反転してから読み取ることです。しかし、これにはリストの変更が含まれますが、これは悪いことです。
または、リストのコピーを作成してから逆にすることもできますが、これには追加の O(n) メモリが使用されます。余分なメモリを使用せず、リストを変更せず、O(n) 時間で実行されるより良い方法はありますか

逆リンクリストのコードは、C# では次のようになります。

Void Reverse (Node head)
{
    Node prev= null;
    Node current = head;
    Node nextNode = null;

        while (current!=null)
        {
            nextNode = current.Next;
            current.Next = prev;
            prev=current;
            current = nextNode; 

        }
        head = prev;

}

再帰的な解決策は

void ReadBackWard (Node n)
{
    if (n==null)
        return;
    else
        ReadBackward(n.Next);

    Console.WriteLine(n.Data);

}

score 11 · Accepted Answer

単一リンクリストの特徴の1つは、実際には単一リンクリストであるということです。それは一方通行であり、それを他の何か（逆の単一リンクリスト、スタック、二重リンクリストなど）に変えない限り、それを克服する方法はありません。人は物事の性質に忠実でなければなりません。

先に指摘したように、リストを両方の方法でトラバースする必要がある場合。二重にリンクされたリストが必要です。それは二重にリンクされたリストの性質であり、それは双方向に行きます。

score 3 · Accepted Answer

O(log(n))今回はメモリとO(n log(n))時間を使用するため、マークの回答の2つのソリューションの中間を占める3番目のソリューションがあります。

これは事実上、バイナリツリー [ ] の逆順降下ですが、各ステップでツリー [ ]O(log(n))の最上位を見つける必要がある点が異なります。O(n)

リストを 2 つに分割する
リストの後半に再帰する
中点の値を出力します
前半に戻る

Pythonでの解決策は次のとおりです（C＃はわかりません）：

def findMidpoint(head, tail):
  pos, mid = head, head
  while pos is not tail and pos.next is not tail:
    pos, mid = pos.next.next, mid.next
  return mid

def printReversed(head, tail=None):
  if head is not tail:
    mid = findMidpoint(head, tail)
    printReversed(mid.next, tail)
    print mid.value,
    printReversed(head, mid)

これは、再帰の代わりに反復を使用して再キャストできますが、明確さが犠牲になります。

たとえば、100 万エントリのリストの場合、3 つのソリューションは次の順序になります。

ソリューション メモリ パフォーマンス
=========================================
 Marc #1 4MB 100 万回の操作
  鉱山 80B 2000 万回の操作
 Marc #2 4B 1兆オペレーション

score 3 · Accepted Answer

void reverse_print(node *head) 
{
    node *newHead = NULL, *cur = head;

    if(!head) return;

    // Reverse the link list O(n) time O(1) space
    while(cur){
        head = head->next;
        cur->next = newHead;
        newHead = cur;
        cur = head;
    }

    // Print the list O(n) time O(1) space
    cur = newHead;
    while(cur) {
        printf(" %d", cur->val);
        cur = cur->next;
    }

    // Reverse the link list again O(n) time O(1) space
    cur = newHead;
    while(cur){
        newHead = newHead->next;
        cur->next = head;
        head = cur;
        cur = newHead;
    }
    // Total complexity O(n) time O(1) space
}

score 1 · Accepted Answer

単一リンクリストが IEnumerable<T> を実装すると仮定すると、LINQ の逆拡張メソッドを利用できます。

var backwards = singlyLinkedList.Reverse();

using System.Linq;LINQ の拡張メソッドを使用するには、コードファイルの先頭にディレクティブを追加する必要があります。

score 1 · Accepted Answer

スタックを作成し、すべての要素をスタックにプッシュするバリエーションは、再帰 (およびシステムの組み込みスタック) を使用することです。次の理由:

それはあなたが再帰をgrokしたことを示しています
コードが少なく、よりエレガントに見えます
素朴な面接担当者は、頭上にスペースがあることに気付かない場合があります (この場合は、そこで働きたいかどうかを検討することをお勧めします)。

score 0 · Accepted Answer

Explicit Stack プログラムで、各ノードのデータだけのスタックを作成する場合 (タイプの Stack を作成する代わりに、タイプの Stack<Node>を作成します<T>)、さらに良いのではないでしょうか? ノードの他の情報を保存する必要がないためです。

IEnumerable<T> Reverse (Node<T> head) {
    Stack<T> nodes = new Stack<T>();
    while(head != null) {
        nodes.Push(head.data);
        head = head.Next;
    }
    while(nodes.Count > 0) {
        yield return nodes.Pop();
    }
}

score 0 · Accepted Answer

これは面倒ですが、機能します：

class SinglyLinkedList {
SinglyLinkedList next;
int pos;
SinglyLinkedList(int pos) {
    this.pos = pos;
}
SinglyLinkedList previous(SinglyLinkedList startNode) {
    if (startNode == this) return null;
    if (startNode.next == this) return startNode;
    else return previous(startNode.next);
}

static int count = 0;
static SinglyLinkedList list;
static SinglyLinkedList head;
static SinglyLinkedList tail;
public static void main (String [] args) {
    init();

    System.out.println("Head: " + head.pos);
    System.out.println("Tail: " + tail.pos);

    list = head;
    System.out.print("List forwards: ");
    while (list != null) {
        System.out.print(list.pos + ",");
        list = list.next;
    }

    list = tail;
    System.out.print("\nList backwards: ");
    while (list.previous(head) != null) {
        System.out.print(list.pos + ",");
        list = list.previous(head);
    }
}
static void init() {
    list = new SinglyLinkedList(0);
    head = list;
    while (count < 100) {
        list.next = new SinglyLinkedList(++count);
        list = list.next;
    }
    tail = list;
}

}

score -1 · Accepted Answer

どうしたの：

    public void printBackwards(LinkedList sl){    
        ListIterator<Element> litr = sl.listIterator(sl.size());
        Element temp;
        while(litr.previousIndex() >= 0){
            temp = litr.previous();
            System.out.println(temp);
        }
    }

O(n) のパフォーマンス、O(1) のメモリ、そしてドレミのようにシンプル！

c# - 単一リンクリストを逆方向に読む方法は?

13 に答える 13

Related

Reference