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

（免責(zé)聲明：下面的解法純屬娛樂 ，另外，示例代碼未經(jīng)編譯和調(diào)試，許多想法未經(jīng)實(shí)踐驗(yàn)證。）

查找鏈表當(dāng)中倒數(shù)第N個節(jié)點(diǎn)。

解法一

逐層遞歸，遍歷到最后一個節(jié)點(diǎn)，并從返回的節(jié)點(diǎn)一次向后遞歸，遍歷N次，找到倒數(shù)第N個節(jié)點(diǎ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． 時間復(fù)雜度為O(index * n)，n為鏈表的長度。

3． 性能開銷較大。

解法二（解法一的變形）

每當(dāng)遍歷到當(dāng)前節(jié)點(diǎn)，即再循環(huán)向后遍歷n個，如果節(jié)點(diǎn)遍歷到最后，并且index自減等于0，說明當(dāng)前節(jié)點(diǎn)即為要找的倒數(shù)第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; 
}