递归算法中的链表操作

今天，打算将问题深入一下，即添加相应的操作在递归的过程中。

（免责声明：下面的解法纯属娱乐 ，另外，示例代码未经编译和调试，许多想法未经实践验证。）

查找链表当中倒数第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; 


} 

分析：与解法一一样。