재귀를 사용하여 단일 연결 목록에서 n 번째 노드에서 마지막 노드 찾기

Question

이 질문은 이미 질문되었지만 재귀를 사용하여 해결하고 싶습니다. 리스트의 각 노드는 정수 값 (int val)을 포함합니다. 정수 값을 반환하고 싶습니다. 그냥 인쇄하는 것이 아닙니다. 나는 다음과 같은 내놓았다 : 나는리스트의 마지막에 도달하면

int findKthNode (node* head, int n){ 
    if(!head) 
     return 1; 
    int retval = findkthNode(head->next, n); 
    if(retval==n) 
     return head->val; 
    return 1+retval; 
} 

, 나는 내가 끝에서 n 번째 노드에 도달 할 때까지 나는 이전의 반환 값에 1을 추가 그 후 1을 반환합니다. 그 시점에서 그 노드에서 int 값을 반환합니다. 이 접근법에는 한 가지 문제점이 있습니다. 첫 번째 통화로 돌아갈 때까지 1을 계속 추가합니다. 그래서 내 목록이 1,5,10204080100이라면 돌아 오기 전에 1 5 번 더 추가 할 것이므로 80 대신 n = 2로 85를 반환하게됩니다. 어떻게 해결할 수 있을까요?

또한 이것이 가능한지 확실하지 않지만 재귀를 사용하여 n 번째 마지막 노드에 대한 포인터를 반환하는 방법이 있습니다. 나는 하나의 연결된 목록으로 이것을 할 수있는 방법을 볼 수 없습니다.

Answer 1

두 가지 다른 변수에 대해 동일한 변수를 사용하지 마십시오. 두 개의 다른 변수를 사용하십시오. 끝에서부터 얼마나 많은 노드를 추적하기 위해 참조로 정수를 전달하고 결과에 대한 리턴을 사용하십시오.

node* findKthNode (node* head, int find, int& found){ 
    if(!head) { 
     found = 1; 
     return head; 
    } 
    node* retval = findkthNode(head->next, find, found); 
    if(found==find) 
     retval = head; 
    found = found + 1; 
    return retval; 
} 

Answer 2

두 개의 "반환 값"이 필요합니다. 하나는 리턴 값이고 다른 하나는 리턴 된 깊이입니다. 깊이를 "반환"하려면 int* depth 매개 변수를 메서드 서명에 추가합니다.

Answer 3

다음 노드는 마지막 노드에서 n 번째 노드에 대한 포인터를 반환하거나 노드가 충분하지 않은 경우 NULL을 반환합니다.

node* findKthNode(node* head, int n) 
{ 
    node* rslt = NULL; 
    doFind(head, n, &rslt); 
    return rslt; 
} 

int doFind(node* head, int n, node** rslt) 
{ 
    if (head == NULL) 
    { 
     return 0; 
    } 
    int ret = doFind(head->next, n, rslt); 
    if (ret == n) 
    { 
     *rslt = head; 
    } 
    return ret + 1; 
} 

이 경우 n은 0 기준입니다. 목록 끝에있는 항목을 찾으려면 다음과 같이 작성하십시오.

node* rslt = findKthNode(head, 0);