算法之递归(3) 链表操作

算法之递归(3)- 链表操作

递归(2)尝试了一个单链表的遍历,同时又分析了如何添加自己的操作,是在递归调用之前,还是在递归调用之后。

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

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

查找链表当中倒数第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/p/2617417.html