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

Lucas for 京东 · February 09, 2015 · Last by 思寒_seveniruby replied at February 09, 2015 · 1055 hits
本帖已被设为精华帖!

算法之递归(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 条回复 时间 点赞

这又是一个合集。

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

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

需要 Sign In 后方可回复, 如果你还没有账号请点击这里 Sign Up