자바에서 재귀를 사용하여 단일 링크 된 목록의 마지막 요소를 찾기위한 알고리즘을 구현할 수 있습니까

Question

나는이 목록에서 반복적으로이 질문을 반복적으로 해결할 수 있음을 알고 있습니다. ; 또한 arraylist를 생성하고 내부의 각 노드에서 발견 된 데이터를 설정합니다. 연결된 목록의 꼬리에 도달하면 arraylist의 요소 수에서 N 번째 항을 뺀 값을 얻으면 답을 얻을 수 있습니다. 그러나 누군가 재귀를 사용하여 이것을 어떻게 수행합니까? 가능한가? 그렇다면 천재성을 나타내는 코드를 보여주세요 :).

참고 :이 내가 온라인으로 발견 간단한 질문했지만, 난 재귀 조각을 추가 :

편집 : 나는 (] 당신이 포인터를 재생할 수 있습니다, ++ 있지만 C/C에서) 자바에서 두 값을 반환 할 수 없습니다 알고 Java로는 불가능할 수도 있다는 것을 알게되었습니다.

Answer 1

그래,이 트릭을해야한다고 생각해. 이것은 C++에 있지만 쉽게 Java으로 번역되어야합니다. 나는 또한 테스트하지 않았다.

Node *NToLastHelper(Node *behind, Node *current, int n) { 
    // If n is not yet 0, keep advancing the current node 
    // to get it n "ahead" of behind. 
    if (n != 0) { 
    return NToLastHelper(behind, current->next, n - 1); 
    } 
    // Since we now know current is n ahead of behind, if it is null 
    // the behind must be n from the end. 
    if (current->next == nullptr) { 
    return behind; 
    } 
    // Otherwise we need to keep going. 
    return NToLastHelper(behind->next, current->next, n); 
} 

Node *NToLast(Node *node, int n) { 
    // Call the helper function from the head node. 
    return NToLastHelper(node, node, n); 
} 

편집 : 노드가 null의 경우

int NToLast(Node *node, int n) { 
    // Call the helper function from the head node. 
    return NToLastHelper(node, node, n)->val; 
} 

이 코드는 심하게 실패합니다 : 마지막 노드의 값을 반환하려는 경우, 당신은 그냥가 변경할 수 있습니다.

Answer 2

일반적으로 루프를 사용하여 수행 할 수있는 모든 작업은 합리적인 언어로 재귀를 통해 수행 할 수도 있습니다. 솔루션의 우아함은 크게 다를 수 있습니다. 다음은 꽤 자바 관용적 인 버전입니다. 간결함을 위해 일반적인 접근 자 기능을 생략했습니다.

여기에있는 아이디어는 목록의 끝까지 되풀이하고 재귀가 푸는 동안 카운터를 증가시키는 것입니다. 카운터가 원하는 값에 도달하면 해당 노드를 반환합니다. 그렇지 않은 경우는 null을 리턴합니다. null가 아닌 값은 맨 위까지 모두 반환됩니다. 목록을 한 번, 한 번 올리십시오. 최소한의 인수. 아담이 의도 한 것을 무시하는 것은 아니지만, 이것은 다소 단순하다고 생각합니다.

NB : Java가 하나의 값만 반환 할 수 있다는 OP의 진술은 사실이지만 그 값은 모든 객체가 될 수 있기 때문에 원하는대로 필드 나 배열 요소가있는 객체를 반환 할 수 있습니다. 그러나 여기서는 필요하지 않았습니다.

public class Test { 

    public void run() { 
     Node node = null; 

     // Build a list of 10 nodes. The last is #1 
     for (int i = 1; i <= 10; i++) { 
      node = new Node(i, node); 
     } 

     // Print from 1st last to 10th last. 
     for (int i = 1; i <= 10; i++) { 
      System.out.println(i + "th last node=" + node.nThFromLast(i).data); 
     } 
    } 

    public static void main(String[] args) { 
     new Test().run(); 
    } 
} 

class Node { 
    int data; // Node data 
    Node next; // Next node or null if this is last 

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

    // A context for finding nth last list element. 
    private static class NthLastFinder { 
     int n, fromLast = 1; 

     NthLastFinder(int n) { 
      this.n = n; 
     } 

     Node find(Node node) { 
      if (node.next != null) { 
       Node rtn = find(node.next); 
       if (rtn != null) { 
        return rtn; 
       } 
       fromLast++; 
      } 
      return fromLast == n ? node : null; 
     } 
    } 

    Node nThFromLast(int n) { 
     return new NthLastFinder(n).find(this); 
    } 
} 

Answer 3

트릭은 재귀 이후 작업을 수행하는 것입니다. private 메소드의 배열은 기본적으로 변경 가능한 정수에 대한 참조로 사용됩니다.

class Node { 
    Node next; 
    int data; 

    public Node findNthFromLast(int n) { 
    return findNthFromLast(new int[] {n}); 
    } 

    private Node findNthFromLast(int[] r) { 
    Node result = next == null ? null : next.findNthFromLast(r); 
    return r[0]-- == 0 ? this : result; 
    } 
} 

Answer 4

재귀 함수 :

int n_to_end(Node *no, int n, Node **res) 
{ 
    if(no->next == NULL) 
    { 
      if(n==0) 
        *res = no; 
      return 0; 
    } 
    else 
    { 
      int tmp = 1 + n_to_end(no->next, n, res); 
      if(tmp == n) 
        *res = no; 
      return tmp; 
    } 
} 

래퍼 함수 :

Node *n_end(Node *no, int n) 
{ 
    Node *res; 
    res = NULL; 
    int m = n_to_end(no, n, &res); 
    if(m < n) 
    { 
      printf("max possible n should be smaller than or equal to: %d\n", m); 
    } 
    return res; 
} 

호출 함수 :

int main() 
{ 
    List list; 
    list.append(3); 
    list.append(5); 
    list.append(2); 
    list.append(2); 
    list.append(1); 
    list.append(1); 
    list.append(2); 
    list.append(2); 

    Node * nth = n_end(list.head, 6); 
    if(nth!=NULL) 
    printf("value is: %d\n", nth->val); 
} 

이 코드는 다른 입력에서 테스트되었다. C++ 버전이긴하지만 논리를 이해할 수 있어야합니다.