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

分析：与解法一一样。

解法三

定义一个全局变量，用来计数，当递归从最后一个节点返回时，计数器减减，当等于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

转载于:https://www.cnblogs.com/lucasluo/archive/2012/07/31/2617417.html

你可能感兴趣的文章