초기 목록을 삭제하지 않고 목록을 뒤집습니다.

Question

목록을 뒤집어 쓰려고하지만 초기 목록을 유지하고 싶습니다. 내 기능 역은 내가이 역 할 예를 들어 초기 목록

을 유지하지 않습니다

Node n = new Node(1,new Node(12, new Node(34, new Node(3, Node.NIL)))); 

을 내 기능은 다음과 같습니다

public Node reverse(){ 

    Node p= this; 
    if(p == NIL) 
     return Node.NIL; 


    if(p.n == Node.NIL) 
     return p; 

    Node rest = p.getNext(); 
    p.setNext(Node.NIL); 
    Node reverseRest = rest.reverse(); 

    rest.setNext(p); 
    return reverseRest; 
} 

역 후 나의 오래된 목록의 길이 1이고,이 예제에서는 4가되기를 원합니다. 내 이전 목록과 내 새 목록은 역순으로 동일한 길이를 가져야합니다.

Answer 1

원래 목록을 유지하려면 reverse 메서드는 의 새 Nodes 개체을 만들어야합니다. 기존의 개체를 수정하지 말아야합니다. 당신이 매개 변수를 사용하지 않는 재귀 reverse()를 작성하려는 경우에는 다음과 같이

, 당신은 그것을 할 수 있습니다 :

• 새로운 Node을 확인하고 그것으로이 노드의 콘텐츠를 복사; 이 노드의 다음이 NIL 경우, NIL
• 에 next을 설정
• 그렇지 않으면 이전 단계의 결과를 반환, 다음
• 에 reverse()를 호출 이전 호출에서 반환 값을 가지고, 그 끝
로 이동
• 1 단계에서 끝까지 새 노드를 추가하고 결과를 반환하십시오.

보다 나은 방법은 reverse의 서명을 변경하여 역순으로 만든 노드를 가져 오는 것입니다. 이것은 수정되지 않은 알고리즘이 O (n) 인 동안 O (n) 알고리즘을 생성합니다.

Answer 2

public Node reverse(){ 


    Node p= this; 
    Node firstDuplicate = new Node(p.getItem()); //save reference for first node to return 
    Node currentDuplicate=firstDuplicate; 

    while(Node.NIL!=p.getNext()){ 
     Node nextNode = p.getNext(); 
     Node nextCopy = new Node(nextNode.getItem()); 
     currentDuplicate.n = nextCopy; 
     currentDuplicate = nextCopy; 
     p = nextNode; 
    } 

       /* If the list is empty */ 
       if(firstDuplicate == NIL) 
        return Node.NIL; 

       /* If the list has only one node */ 
       if(firstDuplicate.n == Node.NIL) 
        return firstDuplicate; 

       Node rest = new Node(); 
       rest = firstDuplicate.getNext(); 

       firstDuplicate.setNext(Node.NIL); 

      Node reverseRest=new Node(); 
       reverseRest = rest.reverse(); 

       /* Join the two lists */ 
       rest.setNext(firstDuplicate); 
       return reverseRest; 
      } 
} 

나는 초기 목록을 복제하고 원본을 유지하기 위해 복제본에 대한 작업을 시도했습니다. 하지만 최악의

Answer 3

이 dasblinkenlight의 (핸들을 사랑 해요!) 제안에 따라 재귀 구현 한 것입니다 : "더 나은 방법은 역순으로, 지금까지 만든 노드를 취할 역의 서명을 변경하는 것입니다"

public class Node { 
    private static final Node NIL=null; 

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

    public int getData() { 
     return data; 
    } 

    public Node getNext() { 
     return next; 
    } 

    private int data; 

    private Node next; 

    public String toString() 
    { 
     String s = ""; 
     Node cur = this; 
     while (cur != Node.NIL) { 
      s += cur.data + ","; 
      cur = cur.getNext(); 
     } 
     return s; 
    } 

    /* Where the recursive magic happens */ 
    /* build the reversed list in the parameter 'reversed' */ 
    public Node reverse(Node n, Node reversed) 
    { 
     if (n == Node.NIL) { 
      return reversed; 
     } else { 
      return reverse(n.next,new Node(n.data,reversed)); 
     } 
    } 

    /* Kick off the recursion from the head node */ 
    public Node reverseList() { 
     return reverse(this,Node.NIL); 
    } 

    public static void main (String args[]) { 

     // Create a sample list 
     Node n = new Node(1,new Node(12, new Node(34, new Node(3, Node.NIL)))); 

     System.out.println(n); 
     System.out.println(n.reverseList()); 
    } 

}