题解 | #统计每个月兔子的总数#

#include<stdio.h>
#include<stdlib.h>

typedef struct ListNode ListNode;
struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};

int dig(ListNode* p,int k,ListNode **node) // 向下遍历并回溯
{
    int x;
    if(p->m_pNext == NULL) // 触底回溯，返回当前层数，尾节点为第一层
        return 1;
    else 
    {
        x = dig(p->m_pNext,k,node)+1; // 当前层数是上一层加一
        if(x==k)                      // 到达指定层数,记录指针
            *node = p;                // 注意node是指针的指针，为了保证指针的地址传递
        return x;                     // 回溯至头结点
    }         
}

int main()
{
    ListNode head;
    ListNode *p = &head;
    ListNode *New;
    int n,k;
    
    while(scanf("%d",&n)!=EOF)
    {
        for(;n>0;n--)
        {
            New = (ListNode *)malloc(sizeof(ListNode));
            
            scanf("%d", &(New->m_nKey));
            
            New->m_pNext = NULL;
            p->m_pNext = New;
            p = New;                   
        }
        p = head.m_pNext;
        scanf("%d",&k);
        dig(p,k,&New);
        printf("%d\n",New->m_nKey);
    }
    
    
    
    return 0;
}