算法之递归（3）- 链表操作

序：
递归（2）尝试了一个单链表的遍历，同时又分析了如何添加自己的操作，是在递归调用之前，还是在递归调用之后。
今天，打算将问题深入一下，即添加相应的操作在递归的过程中。

查找链表当中倒数第 N 个节点

（1）解法一
逐层递归，遍历到最后一个节点，并从返回的节点一次向后递归，遍历 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． 性能开销较大。

（2）解法二（解法一的变形）
每当遍历到当前节点，即再循环向后遍历 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;
}

分析：与解法一一样。

（3）解法三
定义一个全局变量，用来计数，当递归从最后一个节点返回时，计数器减减，当等于 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。
像类似于链表这样的操作，基本就是两指针。
于是我重新给了一个方案如下。
（该段代码已经编译、运行及测试通过）

（4）解法四：

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