今天，打算將問題深入一下，即添加相應的操作在遞歸的過程中。

（免責聲明：下面的解法純屬娛樂 ，另外，示例代碼未經編譯和調試，許多想法未經實踐驗證。）

查找鏈表當中倒數第N個節點。

解法一

逐層遞歸，遍歷到最后一個節點，并從返回的節點一次向后遞歸，遍歷N次，找到倒數第N個節點。

private LNode targetNode = null; 
private LNode FindLastNthNode(LNode head, int index) 
{ 
    if (head.Next == null) 
    { 
        return head; 
    } 
 
    FindLastNthNode(head.Next, index); 
 
    LNode tmpNode = head; 
 
    while ((head.Next != null) && (index > 0)) 
    { 
        head = head.Next; 
        index--; 
    } 
 
    if (head.Next == null && index == 0) 
    { 
        targetNode = tmpNode; 
        return targetNode; 
    } 
 
    return targetNode; 
 
} 

分析

1． 額外的全局性的輔助變量。

2． 時間復雜度為O(index * n)，n為鏈表的長度。

3． 性能開銷較大。

解法二（解法一的變形）

每當遍歷到當前節點，即再循環向后遍歷n個，如果節點遍歷到最后，并且index自減等于0，說明當前節點即為要找的倒數第n個。也就是說解法一是從后向前找，而解法二是從前向后找。

private LNode targetNode2 = null; 
 
private LNode FindLastNthNode2(LNode head, int index) 
{ 
    if (head.Next == null) 
        return head; 
 
    LNode tmpNode = head; 
 
    while (head != null && index >= 0) 
    { 
        head = head.Next; 
        index--; 
    } 
 
    if (head == null && index == 0) 
    { 
        targetNode2 = tmpNode; 
        return targetNode2; 
    } 
 
    return targetNode2; 
} 

分析：與解法一一樣。

解法三

private int counter = 0; 
private LNode targetNode2; 
 
private LNode FindLastNthNode2(LNode head, int index) 
{ 
    if (head.Next == null) 
    { 
        counter = index; 
        return head; 
    } 
 
    FindLastNthNode2(head.Next, index); 
 
    counter--; 
 
    if (counter == 0) 
    { 
        targetNode2 = head; 
        return targetNode2; 
    } 
 
    return targetNode2; 
}