京东质量社区 [原创] 算法之递归 (3)- 链表操作

Lucas for 京东 · 2015年02月09日 · 最后由 思寒_seveniruby 回复于 2015年02月09日 · 252 次阅读
本帖已被设为精华帖!

算法之递归(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; }
    }
}
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
共收到 2 条回复 时间 点赞

这又是一个合集。

面试题合集. 哈哈. 链表是面试题必考.

不过现实中用的不是特别多. 最近我在搞建模, 可能会用到树形结构和图处理, 继续期待好文

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册