원본을 변경하지 않고 Java에서 연결된 목록 반전하기

Question

작동하는 연결된 목록을 역전하려고하는데 원본을 인쇄하려고 할 때 오류가 발생합니다 (헤드 만 인쇄합니다). 내 질문은, 왜 원래의 것에 영향을 미칠 것인지입니다. 아래는 제 코드입니다. LinkedList는 내 자신의 클래스이므로 Node도 마찬가지입니다. 반전하기 전에 목록을 인쇄하려고하면 그 목록이 인쇄됩니다.

public static void main(String[] args) { 
    LinkedList list; 
    ... 
    Node head = list.getHead(); 
    Node rev = reverse(head); 
    Node temp = rev; 
    while (temp != null) { 
     System.out.println(temp); 
     temp = temp.next; 
    } 

    temp = head; 
    while (temp != null) { 
     System.out.println(temp); 
     temp = temp.next; 
    } 
} 

private static reverse(Node head) { 
    // Reversing the linked list 
} 

편집 : 이것은 자바 일 것 같습니다. Java는 참조로 객체를 전달합니다. head를 매개 변수로 전달하면 참조로 전달되고 그에 대한 변경 사항은 호출 함수에 반영됩니다. 노드 h = head를 수행하고 h를 매개 변수로 전달하면 h가 머리와 동일한 객체가되므로 아무 것도 작동하지 않습니다. 내가 생각할 수있는 유일한 방법은 새 개체를 만들고 링크 된 목록을 복사 한 다음이를 매개 변수로 전달하는 것입니다.

제 질문은 더 좋은 해결책입니까? 당신은, 당신은 점점 객체 '는'머리를 얻는 경우에

Answer 1

그것을 이해하려면 그림 목록이

list (list.head =a) --> a (a.next=b) --> b (b.next= c) -> c (c.next = null) 

것 같습니다. 그러면 'a'개체가 수정됩니다. 이렇게하면 목록을 편집하고있는 것을 볼 수 있습니다. 당신이해야 할 일은

은 다음과 같습니다 는 그것이 마지막 그래서

에 당신 이후에 가입 역 복사 다음 항목을 가져 오기 복사본을 역 사본을 작성 머리 를 가져옵니다 가장 쉬운 방법은 reverseNode()가 전달한 복사본 만 편집하고 복사본을 반환하는지 확인하는 것입니다. 먼저 확인하여 노드 클래스는 다른 노드는 다음과 같은 일을 할 복사 생성자가 있습니다

private static Node reverse(Node original) 
{ 
    Node retval = new Node(original); 
    // or you could use clone() as Bhavik suggested, if your Node class implements it 
    // modify retval 
    // I haven't shown code to reverse it as I assume you already have that and you didnt specify if it was a bidirectional list or just one direction. 

    return retval; 
} 

또는 당신은 반전 새 노드를 구성하여 노드 클래스의 정적 메서드 추가 할 수 있습니다 :

를

static Node createReverse(Node n) 
{ 
    return new Node(n.data,n.next,n.prior); 
} 

또는 자체의 역 사본을 리턴하는 노드 클래스의 정적이지 않은 메소드.

그러나 사본에 여전히 기존 목록을 가리키는 포인터가 있기 때문에 매우 추해 보일 수 있습니다.

더 나은 방법은 빈 목록을 새로 작성한 다음 원본의 끝에서 시작하여 사본을 만들어 새 목록의 시작 부분에 추가하는 것입니다.

재귀를 사용할 수 있지만 메모리가 부족할 수 있습니다.

수동으로 수행하는 대신 java.util 패키지를보고 해당 LinkedList 및 목록 항목 유형 중 하나를 사용하도록 전환 할 수 있습니다. 이 수업은 이미이 문제를 해결하면서 모든 문제를 해결했습니다.

다음을 수행 할 수 있습니다 (원래 목록을 그대로 유지해야하는 경우). - 전체 목록을 복사하십시오. - 아래 복사본을 반대로 교환하십시오.

원본을 유지하는 데 신경 쓰지 않는다면 목록에이 방법을 사용하십시오. 그러면 사본을 만들 필요가 없습니다. Collections의에서

:

Collections.reverse(List a_list); 

컬렉션이 양방향인지에 따라 목록을 반대하는 효율적인 방법을 선택합니다 클래스, 단일 방향 등

이

Answer 2

Chunko의 대답은 바로 노드에 대한 참조를 전달하는 대신 노드 사본을 작성해야합니다.

이

LinkedList reversedList = new LinkedList(); 
for (int i = originalList.size()-1; i >= 0; i--) { 
    reversedList.add(list.get(i)); 
} 

자바의 LinkedList이 getHead() 방법이없는, 그래서 당신은 연결리스트의 숙제 관련 사용자 정의 구현을 사용하는 것 같아요 :
는 그러나, 나는 당신이 지나친 것 같아요. 그래도 구현시 을 추가하고 get(int) 메서드를 사용하여 지정된 위치에 항목을 반환하는 add() 메서드를 사용해야합니다.
이러한 메서드를 사용하여 새 목록을 만든 다음 원래 목록의 항목을 역순으로 채울 수 있습니다.