没有合适的资源？快使用搜索试试~ 我知道了~

文库首页后端C#算法大全-面试题-链表-栈-二叉树-数据结构.docx

算法大全-面试题-链表-栈-二叉树-数据结构.docx

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

数据结构

0 下载量 134 浏览量 2023-09-01 16:22:26 上传评论收藏 46KB DOCX 举报

温馨提示

试读

53页

算法大全-面试题-链表-栈-二叉树-数据结构，C#版，主要三大块，一，单链表，二，栈和队列，三，二叉树。每一大块又有许多新鲜好玩的玩法，你会很喜欢的会上瘾的。适合玩算法的朋友。

资源推荐

资源详情

资源评论

一、单链表

1.单链表反转

2.找出单链表的倒数第 4 个元素

3.找出单链表的中间元素

4.删除无头单链表的一个节点

5.两个不交叉的有序链表的合并

6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序把

这个二级链表称一级单链表。

7.单链表交换任意两个元素（不包括表头）

8.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？

9.判断两个单链表是否相交

10.两个单链表相交，计算相交点

11.用链表模拟大整数加法运算

12.单链表排序

13.删除单链表中重复的元素

首先写一个单链表的 C#实现，这是我们的基石：

public class Link

{

public Link Next;

public string Data;

public Link(Link next, string data)

{

this.Next = next;

this.Data = data;

}

其中，我们需要人为地在单链表前面加一个空节点，称其为 head。例如，一个

单链表是 1->2->5，如图所示：

对一个单链表的遍历如下所示：

static void Main(string[] args)

{

Link head = GenerateLink();

Link curr = head;

while (curr != null)

{

Console.WriteLine(curr.Data);

curr = curr.Next;

}

1.单链表反转

这道题目有两种算法，既然是要反转，那么肯定是要破坏原有的数据结构的：

算法 1：我们需要额外的两个变量来存储当前节点 curr 的下一个节点 next、再下

一个节点 nextnext：

public static Link ReverseLink1(Link head)

{

Link curr = head.Next;

Link next = null;

Link nextnext = null;

//if no elements or only one element exists

if (curr == null || curr.Next == null)

{

return head;

}

//if more than one element

while (curr.Next != null)

{

next = curr.Next; //1

nextnext = next.Next; //2

next.Next = head.Next; //3

head.Next = next; //4

curr.Next = nextnext; //5

}

return head;

}

算法的核心是 while 循环中的 5 句话

我们发现，curr 始终指向第 1 个元素。

此外，出于编程的严谨性，还要考虑 2 种极特殊的情况：没有元素的单链表，以

及只有一个元素的单链表，都是不需要反转的。

算法 2：自然是递归

如果题目简化为逆序输出这个单链表，那么递归是很简单的，在递归函数之后输

出当前元素，这样能确保输出第 N 个元素语句永远在第 N+1 个递归函数之后执

行，也就是说第 N 个元素永远在第 N+1 个元素之后输出，最终我们先输出最后

一个元素，然后是倒数第 2 个、倒数第 3 个，直到输出第 1 个：

public static void ReverseLink2(Link head)

{

if (head.Next != null)

{

ReverseLink2(head.Next);

Console.WriteLine(head.Next.Data);

}

但是，现实应用中往往不是要求我们逆序输出（不损坏原有的单链表），而是把

这个单链表逆序（破坏型）。这就要求我们在递归的时候，还要处理递归后的逻

辑。

首先，要把判断单链表有 0 或 1 个元素这部分逻辑独立出来，而不需要在递归中

每次都比较一次：

public static Link ReverseLink3(Link head)

{

//if no elements or only one element exists

if (head.Next == null || head.Next.Next == null)

return head;

head.Next = ReverseLink(head.Next);

return head;

}

我们观测到：

head.Next = ReverseLink(head.Next);

这句话的意思是为 ReverseLink 方法生成的逆序链表添加一个空表头。

接下来就是递归的核心算法 ReverseLink 了：

static Link ReverseLink(Link head)

{

if (head.Next == null)

return head;

Link rHead = ReverseLink(head.Next);

head.Next.Next = head;

head.Next = null;

return rHead;

}

算法的关键就在于递归后的两条语句：

head.Next.Next = head; //1

head.Next = null; //2

啥意思呢？画个图表示就是：

这样，就得到了一个逆序的单链表，我们只用到了 1 个额外的变量 rHead。

2.找出单链表的倒数第 4 个元素

这道题目有两种算法，但无论哪种算法，都要考虑单链表少于 4 个元素的情况：

第 1 种算法，建立两个指针，第一个先走 4 步，然后第 2 个指针也开始走，两个

指针步伐（前进速度）一致。

static Link GetLast4thOne(Link head)

{

Link first = head;

Link second = head;

for (int i = 0; i < 4; i++)

{

if (first.Next == null)

throw new Exception("Less than 4 elements");

first = first.Next;

}

while (first != null)

{

first = first.Next;

second = second.Next;

}

return second;

}

第 2 种算法，做一个数组 arr[4]，让我们遍历单链表，把第 0 个、第 4 个、第 8

个……第 4N 个扔到 arr[0]，把第 1 个、第 5 个、第 9 个……第 4N+1 个扔到

arr[1]，把第 2 个、第 6 个、第 10 个……第 4N+2 个扔到 arr[2]，把第 3 个、第 7

个、第 11 个……第 4N+3 个扔到 arr[3]，这样随着单链表的遍历结束，arr 中存

储的就是单链表的最后 4 个元素，找到最后一个元素对应的 arr[i] ，让

k=(i+1)%4，则 arr[k]就是倒数第 4 个元素。

static Link GetLast4thOneByArray(Link head)

{

Link curr = head;

int i = 0;

Link[] arr = new Link[4];

while (curr.Next != null)

{

arr[i] = curr.Next;

curr = curr.Next;

i = (i + 1) % 4;

}

if (arr[i] == null)

throw new Exception("Less than 4 elements");

return arr[i];

}

本题目源代码下载：

推而广之，对倒数第 K 个元素，都能用以上 2 种算法找出来。

3.找出单链表的中间元素

算法思想：类似于上题，还是使用两个指针 first 和 second，只是 first 每次走一

步，second 每次走两步：

static Link GetMiddleOne(Link head)

{

Link first = head;

Link second = head;

while (first != null && first.Next != null)

{

first = first.Next.Next;

second = second.Next;

}

return second;

}

但是，这道题目有个地方需要注意，就是对于链表元素个数为奇数，以上算法成

立。如果链表元素个数为偶数，那么在返回 second 的同时，还要返回 second.Next

也就是下一个元素，它俩都算是单链表的中间元素。

下面是加强版的算法，无论奇数偶数，一概通杀：

static void Main(string[] args)

{

Link head = GenerateLink();

bool isOdd = true;

Link middle = GetMiddleOne(head, ref isOdd);

if (isOdd)

{

Console.WriteLine(middle.Data);

剩余52页未读，继续阅读

评论收藏

内容反馈

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

小小哭包

粉丝: 1900
资源: 3860

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

算法大全-面试题-链表-栈-二叉树-数据结构.docx

C语言程序设计-职工信息管理系统(链表).docx

算法大全-面试题-链表-栈-二叉树-数据结构

算法大全-面试题-数据结构

常用算法链表堆栈二叉树.docx

delphi.数据结构.链表-电脑资料.docx

算法-数据结构和算法-8-双向链表.rar

数据结构算法-习题-答案-带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点注意不设头指针.docx

算法设计-实验五-链表.docx

数据结构试验(链表，栈，二叉树等多种算法完整试验)

数据结构课程设计 平衡二叉树 链表 图算法 文档.doc

算法与数据结构-二叉树的建立与遍历.docx

数据结构算法演示 顺序.链表.二叉树.广义表.图.堆栈.串

严蔚敏《数据结构》源码 顺序表——二叉树

python算法-数组和链表 数组和链表.pdf

一、基础数据结构-1.链表-2.静态链表

ILSpy 安装包和压缩包

DevExpress22.X完美Patch资源

基于C#与Sql Server的智慧星学生选课管理系统.rar

CefFlashBrowser - Flash浏览器

Prolific USB-to-Serial Comm Port

HslCommunication.dll 7.0.1 免费版本 全部源代码和测试工程

C#使用 MQTTnet 快速实现 MQTT 通信 Demo

vscode 1.77 安装包

StockMonitorInstaller-1.0.13

最新资源

数据结构课程设计平衡二叉树链表图算法文档.doc

数据结构算法演示顺序.链表.二叉树.广义表.图.堆栈.串

严蔚敏《数据结构》源码顺序表——二叉树

python算法-数组和链表数组和链表.pdf

HslCommunication.dll 7.0.1 免费版本全部源代码和测试工程