voidメソッドを使用してリンクリストを再帰的に逆変換する方法はありますか？

Question

voidメソッドを使用してリンクリストを反転する際に問題があります。 Imは2つのポインタノード（p、q）を使用していました。私はいくつかの方法を見つけましたが、無効な方法は見つかりませんでした。私はルートリストを自分自身で変更する必要があります（なぜそれがvoidメソッドでなければならないのですか）。メソッドは再帰的でなければなりません（私は基本定義がvoidメソッドでは異なることを知っています）。ここで私がこれまでにやったことはありません。

パブリックメソッド：

public void reverse(){ 
     reverse(first, null); 
    } 

プライベートメソッド：

private void reverse(Node p, Node q){ 
    if(p.next!=null) 
     reverse(p.next,p); 
    p.next=q; 
} 

Answer 1

あなたのコードは素晴らしい作品！正しくテストしていない可能性があります。ここで私はそれをテスト方法は次のとおりです。

public static void main(String[] args) { 
    Node last = new Node(4, null); 
    Node first = new Node(1, new Node(2, new Node(3, last))); 

    System.out.println("before: " + first); 
    Node.reverse(first); 
    System.out.println("after: " + last); 
} 

private static class Node { 
    private int val; 
    private Node next; 
    public Node(int v, Node n) { val = v; next = n; } 
    public String toString() { return val + (next == null ? "" : " -> " + next); } 

    public static void reverse(Node first) { 
     reverse(first, null); 
    } 
    private static void reverse(Node p, Node q) { 
     if (p.next != null) 
      reverse(p.next, p); 
     p.next = q; 
    } 
} 

出力

before: 1 -> 2 -> 3 -> 4 
after: 4 -> 3 -> 2 -> 1 

---

編集：あなたのpublic reverseはそれを返すことができるようにする方法getLast()を追加し、呼び出し元のコードにlastの必要性を回避するには逆転が終了したとき。 Javaは値渡しのみであるため、firstという呼び出し元の値をメソッドreverseの内部から変更することはできません。次のように変更してください。

// in Node 
private Node getLast() { return next == null ? this : next.getLast(); } 
public static Node reverse(Node first) { 
    Node last = first.getLast(); 
    reverse(first, null); 
    return last; 
} 

// in main() 
System.out.println("before: " + first); 
first = Node.reverse(first); // update the value of first afterwards 
System.out.println("after: " + first);