読み方単独リンクリストの後退か?

StackOverflow https://stackoverflow.com/questions/1116720

  •  12-09-2019
  •  | 
  •  

質問

一方で私の思いは、逆にリストします。ここに一覧です。
してやっていたのでコピーのリストおよびその逆で、この用途追加的にはO(n)。がより良い方法を使用しないメモリな変更のリストとO(n)時間

逆リンクリストコードのようなことにでもマージエレメント

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);

}
役に立ちましたか？

解決

スタックを作成し、O（n）のメモリとO（n）のパフォーマンスを使用します。あなたが前方方向に繰り返すよう、その結果をもたらす、すべてをオフにポップアップ上のすべてを押します。

、O（N ^ 2）の性能（ただし、O（1）余分なメモリ）を使用するには、それはあなたがするようになった最後の前のノードまで、毎回転送読みます。

例：

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

他のヒント

、片方向リンクリストの特徴の一つは、それが、実際には、単独でリンクされていることです。それは一方通行で、あなたは（そのような逆転単独リンクリスト、スタック、二重リンクリスト...として）何か他のものに変えない限り、それを克服する方法はありません。一つは、物事の本質に忠実である必要があります。

以前にも指摘したように、あなたは、リストに両方の方法を通過する必要がある場合。あなたは、二重リンクリストを持っている必要があります。それは二重にリンクされたリストの性質である、それは両方の方法を行くます。

本当にあなたが二重リンクリストを使用する必要があります。

これが不可能な場合、私はあなたの最良の選択肢が逆転されたリストのコピーを構築することになると思います。

リストが長すぎる場合（効果的にスタックにリストをコピーする）、そのような再帰に頼るとして

他のオプションは、あなたがスタック領域が不足することがあります。

メモリーのあなたが短い場合は、リストを逆にそれを反復処理し、再びそれを逆にすることができます。別の方法としては、ノードへのポインタのスタックを作る（またはC＃でポインタのようなもの何でも）することができます。

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
}

この溶液に、この時間を使用 O(log(n)) メモリ O(n log(n)) 時に、このように占領中にソリューションマークの答えです。

で効果的に逆転する系のバイナリーツリー[O(log(n))]を除き、各ステップに必要なものをトップツリーの[O(n)]:

  1. 分割のリスト二
  2. Recurseのリスト
  3. 印刷の価値を中心に
  4. Recurseの前半

こちらではのソリューショ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)

こrecastを繰り返し処理の代わりに再帰が、コストの透明度

たとえば、百万円-記事リストのソリューションのためのもの

Solution   Memory       Performance
=========================================
 Marc #1     4MB    1 million operations
  Mine       80B    20 million operations
 Marc #2      4B    1 trillion operations

あなたの単独リンクリストは、IEnumerableをを実装して、あなたはLINQのリバース拡張メソッドを利用することができますと仮定します：

var backwards = singlyLinkedList.Reverse();

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

の変化をスタックを押してすべての要素のスタックは再帰のシステムの構築、スタックは、こういう生産コードがとり(まぁのインタビューに答え以下の理由

  1. んでいることを示grok再帰
  2. するべきだと思うんでコードが表示されによりエレガント
  3. るナイーブな聞き手に気づいていませんがスペースのオーバーヘッド(この場合もたらすためにするための他のいかなる仕事あります。

さて、素朴な解決策は、あなたがいつもあなただけの左ノードを保存し、そのノードを見つけるまで、最初から反復、その後、現在の位置しているどのノードを追跡することです。そして、あなたは現在の位置しているノードを見つけるたびに、あなたは最初から再度反復、で現在している一人としてそのノードを保存し、あなただけの左ノードを生成します。

このはもちろん恐ろしく悪いパフォーマンスが賢明だろう。

私はいくつかのよりスマートな人々がより良い解決策を持っていると確信しています。

擬似コード（バグとも）

current node = nothing
while current node is not first node
    node = start
    while node is not current node
        previous node = node
        node = next node
    produce previous node
    set current node to previous node

これは厄介ですが、働きます：

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;
}

}

明示的なスタックプログラムでいる場合、我々はそれがより良いではないでしょう（その代わり型<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();
    }
}

あなたはO（N ^ 2）でそれを読むことができる - 毎回読んで最後のノードに移動し、以前の1

を印刷します

と間違って何ます：

    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）メモリと行う-RE-MIのような単純な！

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top