1

線形連結リストはノードのセットです。ノードは次のように定義されます (わかりやすくするために、ノードとリストを区別しません)。

class Node{
    Object data;
    Node link;

    public Node(Object pData, Node pLink){
        this.data = pData;
        this.link = pLink;
    }

    public String toString(){
        if(this.link != null){
            return this.data.toString() + this.link.toString();
        }else{
            return this.data.toString() ;
        }
    }

    public void inc(){
        this.data = new Integer((Integer)this.data + 1);
    }

    public void lappend(Node list){
        Node child = this.link;
        while(child != null){
            child = child.link;
        }
        child.link = list;
    }

    public Node copy(){
        if(this.link != null){
            return new Node(new Integer((Integer)this.data), this.link.copy());
        }else{
            return new Node(new Integer((Integer)this.data), null);
        }
    }

    public Node invert(){
        Node child = this.link;
        while(child != null){
            child = child.link;
        }
        child.link = this;....
    }
}

リストのディープコピーを作成できます。ここで、リストを反転して、最初のノードが最後になり、最後が最初になるようにします。インバーテッド リストはディープ コピーである必要があります。

反転機能の開発を開始しましたが、よくわかりません。何か案は？

更新：線形リンクリストは再帰的なデータ構造であるため、再帰的な方法があるかもしれません。

最初の要素を取得し、子を持たないノードに到達するまでリストを繰り返し処理し、最初の要素を追加します。これを 2 番目、3 番目の要素について繰り返します....

4

8 に答える 8

4

面接で時々こんな質問をされます...

再帰的なソリューションを使用したり、スタックを使用してこれを解決したりすることはお勧めしません。このようなタスクにO(n)メモリを割り当てても意味がありません。

これは簡単なO(1)ソリューションです (今は実行していないので、修正が必要な場合はお詫びします)。

Node reverse (Node current) {

    Node prev = null;

    while (current != null) {
        Node nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }

    return prev;
}

ところで:lappendメソッドは機能しますか? 常に . をスローするようNullReferenceExceptionです。

于 2011-01-13T22:43:50.727 に答える
3

次の観察に基づいて、この問題に対する優れた再帰的解決策があります。

  1. 空リストの逆は空リストです。
  2. シングルトンリストの逆はそれ自体です。
  3. ノード N の後にリスト L が続くリストの逆は、リスト L の後にノード N が続くリストの逆です。

したがって、次の行に沿って疑似コードを使用して逆関数を実装できます。

void reverseList(Node node) {
    if (node == null) return;      // Reverse of empty list is itself.
    if (node.next == null) return; // Reverse of singleton list is itself.

    reverseList(node.next); // Reverse the rest of the list
    appendNodeToList(node, node.next); // Append the new value.
}

このアルゴリズムの単純な実装は O(n 2 ) で実行されます。これは、反転ごとに追加が必要であり、リストの残りに対して O(n) スキャンが必要になるためです。ただし、実際には、巧妙な観察を使用して O(n) でこれを機能させることができます。次のようなリンク リストがあるとします。

n1 --> n2 --> [rest of the list]

n2 から始まるリストを逆にすると、次の設定になります。

n1       [reverse of rest of the list] --> n2
 |                                          ^
 +------------------------------------------+

したがって、 n1 を指すように、逆方向リストの新しい末尾であるn1.next.next = n1を設定することにより、リストの残りの逆方向に n1 を追加できます。n2

[reverse of the rest of the list] --> n2 --> n1

そして、あなたは金色です！再び擬似コード:

void reverseList(Node node) {
    if (node == null) return;      // Reverse of empty list is itself.
    if (node.next == null) return; // Reverse of singleton list is itself.

    reverseList(node.next); // Reverse the rest of the list
    node.next.next = node; // Append the new value.
}

EDIT：Ranが指摘したように、これはそのストレージスペースにコールスタックを使用するため、スタックオーバーフローのリスクがあります。代わりに明示的なスタックを使用する場合は、次のようにできます。

void reverseList(Node node) {
    /* Make a stack of the reverse of the nodes. */
    Stack<Node> s = new Stack<Node>();
    for (Node curr = node; node != null; node = node.next)
        s.push(curr);

    /* Start unwinding it. */
    Node curr = null;
    while (!s.empty()) {
        Node top = s.pop();

        /* If there is no node in the list yet, set it to the current node. */
        if (curr == null)
            curr = top;
        /* Otherwise, have the current node point to this next node. */
        else
            curr.next = top;

        /* Update the current pointer to be this new node. */
        curr = top;
    }
}

これは、リンクされたリスト要素を同様に反転させると思います。

于 2011-01-13T22:37:49.860 に答える
2

現在のリストをスタックとして扱います(これが私の疑似コードです)。

Node x = copyOf(list.head);
x.link = null;
foreach(node in list){
    Node temp = copyOf(list.head);
    temp.link = x;
    x = temp;        
}

最後xに反転リストの先頭になります。

于 2011-01-13T22:37:21.393 に答える
1

私はもっ​​と家族的な聖霊降臨祭Cですが、それでも試してみましょう。（これがJavaで実行されるかどうかはわかりませんが、実行する必要があります）

node n = (well first one)
node prev = NULL;
node t;
while(n != NULL)
{
     t = n.next;
     n.next = prev;
     prev = n;
     n = t;
}
于 2011-01-13T23:05:54.157 に答える
1

単一リンクのリストを逆にすることは、一種の古典的な質問です。ここでも回答されています（よく回答されています）。参照保持用のレジスタ（または2）以外に、再帰も追加のメモリも必要ありません。ただし、OPにとっては、学校のプロジェクト/宿題であり、いくつかのアドバイスだと思います。実際のデータストレージに単一のリンクリストを使用する場合は、テールノードの使用も検討してください。（現在、単一のリンクされたリストはほとんど消滅していますが、HashMap バケットが思い浮かびます）。「追加」中に何らかの条件についてすべてのノードをチェックする必要がない限り、テールはかなり改善されています。以下は、リバース メソッドとテール ノードを備えたコードです。

package t1;

public class SList {
    Node head = new Node(); 
    Node tail = head;

    private static class Node{
        Node link;
        int data;           
    }


    void add(int i){
        Node n = new Node();
        n.data = i;
        tail = tail.link =n;        
    }

    void reverse(){
        tail = head;
        head = reverse(head);
        tail.link = null;//former head still links back, so clear it
    }

    private static Node reverse(Node head){            
        for (Node n=head.link, link; n!=null; n=link){//essentially replace head w/ the next and relink
            link = n.link;
            n.link = head;
            head = n;           
        }
        return head;
    }

    void print(){
        for (Node n=head; n!=null;n=n.link){
            System.out.println(n.data);
        }       
    }

    public static void main(String[] args) {
        SList l = new SList();
        l.add(1);l.add(2);l.add(3);l.add(4);
        l.print();
        System.out.println("==");
        l.reverse();
        l.print();
    }
}
于 2011-01-14T01:53:04.047 に答える
0

私はそのようなことを考えていました（私はそれをテストしなかったので）：

invert(){
  m(firstNode, null);
}

m(Node v, Node bef){
  if(v.link != null)
   m(v.link,v);
  else
   v.link=bef;
}
于 2011-01-13T22:41:56.493 に答える
0

多くのテストをせずに、

Node head = this;
Node middle = null;
Node trail = null;
while (head != null) {
    trail = middle;
    middle = head;
    head = head.link;
    middle.link = trail;
}
head = middle;
return head;
于 2011-01-13T22:51:24.377 に答える