리뷰나라 - Page 43413 of 45103

[java] 자바에서 연결 목록을 재귀 적으로 뒤집기

나는 한동안 클래스를 위해 Java 프로젝트에서 일하고 있습니다. 이것은 연결 목록 (여기서는라고하며라는 AddressList단순 노드를 포함 함 ListNode) 의 구현입니다 . 문제는 모든 것이 재귀 알고리즘으로 이루어져야한다는 것입니다. 나는 한 가지 방법으로 모든 것을 잘 할 수 있었다.public AddressList reverse()

ListNode :

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에서 재귀 적으로 뒤집어서 자바 코드로 직접 변환 한 알고리즘을 찾았지만 작동했지만 이해하지 못했다.

편집 : 신경 쓰지 마세요, 그동안 알아 냈어요.

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

내가 여기있는 동안이 경로에 문제가있는 사람이 있습니까?

답변

하나의 답장에 그것을 설명하는 코드가 있지만, 작은 질문을하고 답함으로써 밑바닥부터 시작하는 것이 더 쉬울 수 있습니다 (이것은 The Little Lisper의 접근 방식입니다).

null (빈 목록)의 반대는 무엇입니까? 없는.
단일 요소 목록의 반대는 무엇입니까? 요소.
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;
}

답변

인터뷰에서이 질문을 받았는데, 조금 긴장해서 더듬 거려서 짜증이났다.

이것은 reverse (head, NULL)로 호출되는 단일 연결 목록을 뒤집어 야합니다. 그래서 이것이 당신의 목록이라면 :

1-> 2-> 3-> 4-> 5-> null
다음과 같이됩니다.
5-> 4-> 3-> 2-> 1-> null


    //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 개의 편집처럼 끝났고, 그것이 여전히 나를 위해 조금 까다 롭다는 것을 보여줍니다.

답변

나는 절반을 통과했지만 (널이 될 때까지, 주각이 제안한 하나의 노드) 재귀 호출을 한 후 트랙을 잃었습니다. 그러나 주각으로 게시물을 읽은 후 다음과 같이 생각했습니다.

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;
}

답변

여기에 또 다른 재귀 솔루션이 있습니다. 다른 것보다 재귀 함수 내에 코드가 적으므로 조금 더 빠를 수 있습니다. 이것은 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);
    }
}

답변

알고리즘은 다음 모델에서 작업해야합니다.

머리를 추적하다
링크 목록 끝까지 반복
역 연결

구조:

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

답변

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;
}

답변

나는 이것이 오래된 게시물이라는 것을 알고 있지만 대부분의 답변은 꼬리 재귀가 아닙니다. 즉 재귀 호출에서 돌아온 후 일부 작업을 수행하므로 가장 효율적이지 않습니다.

다음은 꼬리 재귀 버전입니다.

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());