算法之递归（3）- 链表操作
递归（2）尝试了一个单链表的遍历，同时又分析了如何添加自己的操作，是在递归调用之前，还是在递归调用之后。
今天，打算将问题深入一下，即添加相应的操作在递归的过程中。
（免责声明：下面的解法纯属娱乐 ，另外，示例代码未经编译和调试，许多想法未经实践验证。）
解法一
逐层递归，遍历到最后一个节点，并从返回的节点一次向后递归，遍历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; }
分析：与解法一一样。
解法三
定义一个全局变量，用来计数，当递归从最后一个节点返回时，计数器减减，当等于0时，这个节点即是要找的倒数第N个节点。
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; }
分析
1． 两个辅助变量。
2． 时间复杂度为O(n)。
3． 多余的index，累赘的counter。
其实以上几个解决方案个人觉得都不够perfect。
像类似于链表这样的操作，基本就是两指针。
于是我重新给了一个方案如下。
（该段代码已经编译、运行及测试通过）
解法四：
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication17 { class Program { static void Main(string[] args) { Node head = new Node() { Data = "Head" }; Node lucas = new Node() { Data = "Lucas" }; Node bill = new Node() { Data = "Bill" }; Node steve = new Node() { Data = "Steve" }; Node anders = new Node() { Data = "Anders" }; Node jordan = new Node() { Data = "Jordan" }; head.Next = lucas; lucas.Next = bill; bill.Next = steve; steve.Next = anders; anders.Next = jordan; Program p = new Program(); Node resultNode = p.FindLastNthNode(head, 2); Console.WriteLine(resultNode.Data); Console.ReadLine(); } private Node FindLastNthNode(Node node, int n) { if(node == null) { return node; } if(n <= 0) { throw new ArgumentException("n"); } Node node1 = node; Node node2 = node; return this.InternalFindLastNthNode(node1, node2, n); } private Node InternalFindLastNthNode(Node node1, Node node2, int n) { if(node1 == null) { return node2; } if(n == 0) { return this.InternalFindLastNthNode(node1.Next, node2.Next, 0); } return this.InternalFindLastNthNode(node1.Next, node2, --n); } } public class Node { public string Data { get; set; } public Node Next { get; set; } } }
Best Regards,
Lucas Luo
原文：http://www.cnblogs.com/devtesters/p/4274473.html