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

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

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

解法一

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

3． 性能開(kāi)銷(xiāo)較大。

解法二（解法一的變形）

每當(dāng)遍歷到當(dāng)前節(jié)點(diǎn)，即再循環(huán)向后遍歷n個(gè)，如果節(jié)點(diǎn)遍歷到最后，并且index自減等于0，說(shuō)明當(dāng)前節(jié)點(diǎn)即為要找的倒數(shù)第n個(gè)。也就是說(shuō)解法一是從后向前找，而解法二是從前向后找。

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; 
}