java - Javaでリンクされたリストを再帰的に逆にする

Question

私はしばらくの間、クラスのJavaプロジェクトに取り組んでいます。これは、リンクされたリスト (ここでは と呼ばれ、 とAddressList呼ばれる単純なノードを含むListNode) の実装です。問題は、すべてを再帰アルゴリズムで行う必要があることです。私はすべてのことを1つの方法でうまく行うことができました：public AddressList reverse()

リストノード:

public class ListNode{
  public String data;
  public ListNode next;
}

現在、私のreverse関数は、再帰を許可する引数を取るヘルパー関数を呼び出すだけです。

public AddressList reverse(){
  return new AddressList(this.reverse(this.head));
}

の署名を持つヘルパー関数を使用しますprivate ListNode reverse(ListNode current)。

現時点では、スタックを使用して繰り返し動作させていますが、これは仕様が要求するものではありません。私は C 言語でアルゴリズムを再帰的に逆にして手動で Java コードに変換するアルゴリズムを見つけましたが、それは機能しましたが、理解できませんでした。

編集：気にしないで、その間にそれを理解しました。

private AddressList reverse(ListNode current, AddressList reversedList){
  if(current == null) 
      return reversedList;
  reversedList.addToFront(current.getData());
  return this.reverse(current.getNext(), reversedList);
}

私がここにいる間、誰かこのルートに何か問題があると思いますか?

Answer 1

それを説明するコードが 1 つの返信に含まれていますが、小さな質問をしたり答えたりすることで、ボトムアップから始める方が簡単だと思うかもしれません (これは The Little Lisper のアプローチです)。

1. null (空のリスト) の逆は何ですか? ヌル。
2. 1要素リストの逆は何ですか? 要素。
3. n要素リストの逆は何ですか? 最初の要素が続くリストの残りの部分の逆。

---

public ListNode Reverse(ListNode list)
{
    if (list == null) return null; // first question

    if (list.next == null) return list; // second question

    // third question - in Lisp this is easy, but we don't have cons
    // so we grab the second element (which will be the last after we reverse it)

    ListNode secondElem = list.next;

    // bug fix - need to unlink list from the rest or you will get a cycle
    list.next = null;

    // then we reverse everything from the second element on
    ListNode reverseRest = Reverse(secondElem);

    // then we join the two lists
    secondElem.next = list;

    return reverseRest;
}

Answer 2

面接でこの質問をされたのですが、少し緊張していたので手探りで悩んでいました。

これは、reverse(head,NULL); で呼び出された単一リンク リストを逆にする必要があります。これがあなたのリストだったら：

1->2->3->4->5->ヌル
それは次のようになります。
5->4->3->2->1->ヌル

    //Takes as parameters a node in a linked list, and p, the previous node in that list
    //returns the head of the new list
    Node reverse(Node n,Node p){   
        if(n==null) return null;
        if(n.next==null){ //if this is the end of the list, then this is the new head
            n.next=p;
            return n;
        }
        Node r=reverse(n.next,n);  //call reverse for the next node, 
                                      //using yourself as the previous node
        n.next=p;                     //Set your next node to be the previous node 
        return r;                     //Return the head of the new list
    }
    

編集：これで6回の編集が行われたように、まだ少しトリッキーであることを示しています笑

Answer 3

私は途中まで（nullまで、および台座によって提案された1つのノードまで）到達しましたが、再帰呼び出しを行った後に追跡を失いました。しかし、台座の投稿を読んだ後、私が思いついたのは次のとおりです。

Node reverse(Node head) {
  // if head is null or only one node, it's reverse of itself.
  if ( (head==null) || (head.next == null) ) return head;

  // reverse the sub-list leaving the head node.
  Node reverse = reverse(head.next);

  // head.next still points to the last element of reversed sub-list.
  // so move the head to end.
  head.next.next = head;

  // point last node to nil, (get rid of cycles)
  head.next = null;
  return reverse;
}

Answer 4

これは、さらに別の再帰的な解決策です。再帰関数内のコードが他の関数よりも少ないため、少し高速になる可能性があります。これは C# ですが、Java も非常に似ていると思います。

class Node<T>
{
    Node<T> next;
    public T data;
}

class LinkedList<T>
{
    Node<T> head = null;

    public void Reverse()
    {
        if (head != null)
            head = RecursiveReverse(null, head);
    }

    private Node<T> RecursiveReverse(Node<T> prev, Node<T> curr)
    {
        Node<T> next = curr.next;
        curr.next = prev;
        return (next == null) ? curr : RecursiveReverse(curr, next);
    }
}

Answer 5

アルゴは次のモデルで動作する必要があります、

• 頭を追跡する
• リンクリストの最後まで再帰
• 逆リンケージ

構造：

Head    
|    
1-->2-->3-->4-->N-->null

null-->1-->2-->3-->4-->N<--null

null-->1-->2-->3-->4<--N<--null

null-->1-->2-->3<--4<--N<--null

null-->1-->2<--3<--4<--N<--null

null-->1<--2<--3<--4<--N<--null

null<--1<--2<--3<--4<--N
                       |
                       Head

コード：

public ListNode reverse(ListNode toBeNextNode, ListNode currentNode)
{               
        ListNode currentHead = currentNode; // keep track of the head

        if ((currentNode==null ||currentNode.next==null )&& toBeNextNode ==null)return currentHead; // ignore for size 0 & 1

        if (currentNode.next!=null)currentHead = reverse(currentNode, currentNode.next); // travarse till end recursively

        currentNode.next = toBeNextNode; // reverse link

        return currentHead;
}

出力：

head-->12345

head-->54321

Answer 6

これはLISPに似たよりクリーンなソリューションだと思います

// Example:
// reverse0(1->2->3, null) => 
//      reverse0(2->3, 1) => 
//          reverse0(3, 2->1) => reverse0(null, 3->2->1)
// once the first argument is null, return the second arg
// which is nothing but the reveresed list.

Link reverse0(Link f, Link n) {
    if (f != null) {
        Link t = new Link(f.data1, f.data2); 
        t.nextLink = n;                      
        f = f.nextLink;             // assuming first had n elements before, 
                                    // now it has (n-1) elements
        reverse0(f, t);
    }
    return n;
}

Answer 7

これが古い投稿であることは知っていますが、ほとんどの回答は末尾再帰的ではありません。つまり、再帰呼び出しから戻った後にいくつかの操作を行うため、最も効率的ではありません。

末尾再帰バージョンは次のとおりです。

public Node reverse(Node previous, Node current) {
    if(previous == null)
        return null;
    if(previous.equals(head))
        previous.setNext(null);
    if(current == null) {    // end of list
        head = previous;
        return head;
    } else {
                    Node temp = current.getNext();
        current.setNext(previous);
        reverse(current, temp);
    }
    return null;    //should never reach here.
} 

電話：

Node newHead = reverse(head, head.getNext());

Answer 8

public Node reverseListRecursive(Node curr)
{
    if(curr == null){//Base case
        return head;
    }
    else{
        (reverseListRecursive(curr.next)).next = (curr);
    }
    return curr;
}

Answer 9

ボイドリバース（ノード1、ノード2）{
if(node1.next!=null)
      逆 (node1.next,node1);
   node1.next=node2;
}
このメソッドを reverse(start,null); として呼び出します。

Answer 10

public void reverse() {
    head = reverseNodes(null, head);
}

private Node reverseNodes(Node prevNode, Node currentNode) {
    if (currentNode == null)
        return prevNode;
    Node nextNode = currentNode.next;
    currentNode.next = prevNode;
    return reverseNodes(currentNode, nextNode);
}

Answer 11

再帰的アルゴリズムによるリバース。

public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;    
    ListNode rHead = reverse(head.next);
    rHead.next = head;
    head = null;
    return rHead;
}

反復による

public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;    
    ListNode prev = null;
    ListNode cur = head
    ListNode next = head.next;
    while (next != null) {
        cur.next = prev;
        prev = cur;
        cur = next;
        next = next.next;
    }
    return cur;
}

Answer 12

Java は常に値渡しであるため、Java で連結リストを再帰的に反転するには、再帰の最後に「新しいヘッド」(反転後のヘッド ノード) を返すようにしてください。

static ListNode reverseR(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode first = head;
    ListNode rest = head.next;

    // reverse the rest of the list recursively
    head = reverseR(rest);

    // fix the first node after recursion
    first.next.next = first;
    first.next = null;

    return head;
}

Answer 13

public static ListNode recRev(ListNode curr){

    if(curr.next == null){
        return curr;
    }
    ListNode head = recRev(curr.next);
    curr.next.next = curr;
    curr.next = null;

    // propogate the head value
    return head;

}

Answer 14

PointZeroTwo はエレガントな答えを得ており、Java でも同じです ...

public void reverseList(){
    if(head!=null){
        head = reverseListNodes(null , head);
    }
}

private Node reverseListNodes(Node parent , Node child ){
    Node next = child.next;
    child.next = parent;
    return (next==null)?child:reverseListNodes(child, next);
}

Answer 15

public class Singlelinkedlist {
  public static void main(String[] args) {
    Elem list  = new Elem();
    Reverse(list); //list is populate some  where or some how
  }

  //this  is the part you should be concerned with the function/Method has only 3 lines

  public static void Reverse(Elem e){
    if (e!=null)
      if(e.next !=null )
        Reverse(e.next);
    //System.out.println(e.data);
  }
}

class Elem {
  public Elem next;    // Link to next element in the list.
  public String data;  // Reference to the data.
}

Answer 16

public Node reverseRec(Node prev, Node curr) {
    if (curr == null) return null;  

    if (curr.next == null) {
        curr.next = prev;
        return curr;

    } else {
        Node temp = curr.next; 
        curr.next = prev;
        return reverseRec(curr, temp);
    }               
}

呼び出し: head = reverseRec(null, head);

Answer 17

private Node ReverseList(Node current, Node previous)
    {
        if (current == null) return null;
        Node originalNext = current.next;
        current.next = previous;
        if (originalNext == null) return current;
        return ReverseList(originalNext, current);
    }

Answer 18

//this function reverses the linked list
public Node reverseList(Node p) {
    if(head == null){
        return null;
    }
    //make the last node as head
    if(p.next == null){
        head.next = null;
        head = p;
        return p;
    }
    //traverse to the last node, then reverse the pointers by assigning the 2nd last node to last node and so on..
    return reverseList(p.next).next = p;
}

Answer 19

再帰的なデータ構造の不変の実装について説明した記事に触発されて、 Swift を使用して別のソリューションをまとめました。

主な回答は、次のトピックを強調することでソリューションを文書化します。

1. nil (空のリスト) の逆は何ですか?
   • Swift には nil 保護があるため、ここでは問題ありません。
2. 1要素リストの逆は何ですか?
   • 要素そのもの
3. n要素リストの逆は何ですか?
   • 最初の要素が続く 2 番目の要素の逆。

以下のソリューションで該当する場合は、これらを呼び出しました。

/**
 Node is a class that stores an arbitrary value of generic type T 
 and a pointer to another Node of the same time.  This is a recursive 
 data structure representative of a member of a unidirectional linked
 list.
 */
public class Node<T> {
    public let value: T
    public let next: Node<T>?

    public init(value: T, next: Node<T>?) {
        self.value = value
        self.next = next
    }

    public func reversedList() -> Node<T> {
        if let next = self.next {
            // 3. The reverse of the second element on followed by the first element.
            return next.reversedList() + value
        } else {
            // 2. Reverse of a one element list is itself
            return self
        }
    }
}

/**
 @return Returns a newly created Node consisting of the lhs list appended with rhs value.
 */
public func +<T>(lhs: Node<T>, rhs: T) -> Node<T> {
    let tail: Node<T>?
    if let next = lhs.next {
        // The new tail is created recursively, as long as there is a next node.
        tail = next + rhs
    } else {
        // If there is not a next node, create a new tail node to append
        tail = Node<T>(value: rhs, next: nil)
    }
    // Return a newly created Node consisting of the lhs list appended with rhs value.
    return Node<T>(value: lhs.value, next: tail)
}

Answer 20

他の人がしたこと、他の投稿ではコンテンツのゲームです。私がしたことは、リンクリストのゲームです。メンバーの値の逆ではなく、LinkedList のメンバーを逆にします。

Public LinkedList reverse(LinkedList List)
{
       if(List == null)
               return null;
       if(List.next() == null)
              return List;
       LinkedList temp = this.reverse( List.next() );
       return temp.setNext( List );
}

Answer 21

static void reverseList(){

if(head!=null||head.next!=null){
ListNode tail=head;//head points to tail


ListNode Second=head.next;
ListNode Third=Second.next;
tail.next=null;//tail previous head is poiniting null
Second.next=tail;
ListNode current=Third;
ListNode prev=Second;
if(Third.next!=null){



    while(current!=null){
    ListNode    next=current.next;
        current.next=prev;
        prev=current;
        current=next;
    }
    }
head=prev;//new head
}
}
class ListNode{
    public int data;
    public ListNode next;
    public int getData() {
        return data;
    }

    public ListNode(int data) {
        super();
        this.data = data;
        this.next=null;
    }

    public ListNode(int data, ListNode next) {
        super();
        this.data = data;
        this.next = next;
    }

    public void setData(int data) {
        this.data = data;
    }
    public ListNode getNext() {
        return next;
    }
    public void setNext(ListNode next) {
        this.next = next;
    }





}

Answer 22

解決策は次のとおりです。

package basic;

import custom.ds.nodes.Node;

public class RevLinkedList {

private static Node<Integer> first = null;

public static void main(String[] args) {
    Node<Integer> f = new Node<Integer>();
    Node<Integer> s = new Node<Integer>();
    Node<Integer> t = new Node<Integer>();
    Node<Integer> fo = new Node<Integer>();
    f.setNext(s);
    s.setNext(t);
    t.setNext(fo);
    fo.setNext(null);

    f.setItem(1);
    s.setItem(2);
    t.setItem(3);
    fo.setItem(4);
    Node<Integer> curr = f;
    display(curr);
    revLL(null, f);
    display(first);
}

public static void display(Node<Integer> curr) {
    while (curr.getNext() != null) {
        System.out.println(curr.getItem());
        System.out.println(curr.getNext());
        curr = curr.getNext();
    }
}

public static void revLL(Node<Integer> pn, Node<Integer> cn) {
    while (cn.getNext() != null) {
        revLL(cn, cn.getNext());
        break;
    }
    if (cn.getNext() == null) {
        first = cn;
    }
    cn.setNext(pn);
}

}

Answer 23

これは、純粋な関数型プログラミング言語である Opal でこれを行う方法です。そして、私見-これを再帰的に行うことは、そのコンテキストでのみ意味があります。

List Reverse(List l)
{
    if (IsEmpty(l) || Size(l) == 1) return l;
    return reverse(rest(l))::first(l);
}

rest(l) は、最初のノードのない元のリストであるリストを返します。first(l) は最初の要素を返します。:: は連結演算子です。