以图明志

数据结构

用快慢指针判断单链表环,找到环入口

扩展到判断两个链表是否相交
快慢指针在解决单链表环问题的时候是非常有用的,下面来探讨一下单链表的环的一些问题。有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。

数据结构

腾讯面试题:快速找到未知长度单链表的中间节点

快慢指针在单链表中很有用处
普通的方法很简单,首先遍历一遍单链表以确定单链表的长度L。然后再次从头节点出发循环L/2次找到单链表的中间节点。算法复杂度为O(L+L/2)=O(3L/2)。能否再优化一下这个时间复杂度呢?有一个很巧妙的方法:设置两个指针*search、*mid都指向单链表的头节点。其中* search的移动速度是*mid的2倍。当*search指向末尾节点的时候,mid正好就在中间了。这也是标尺的思想。

数据结构

[专题] 结构之美:获取单链表倒数第N个结点值

距离——标尺的方法
这是一个比较常见的面试算法题:一次遍历找链表倒数第n个节点。不管是顺数n个还是倒数n个,其实都是距离-标尺问题。标尺是一段距离可以用线段的两个端点来衡量,我们能够判断倒数第一个节点,因为他的next==NULL。如果我们用两个指针,并保持他们的距离为n,那么当这个线段的右端指向末尾节点时,左端节点就指向倒数第n个节点。

数据结构

[专题] 结构之美:判断单链表中是否有环

两种判定方法介绍
有环的定义是,链表的尾节点指向了链接中间的某个节点。比如下图,如果单链表有环,则在遍历时,在通过6之后,会重新回到3,那么我们可以在遍历时使用两个指针,看两个指针是否相等。方法一:使用p、q两个指针,p总是向前走,但q每次都从头开始走,对于每个节点,看p走的步数是否和q一样。

数据结构

[专题] 结构之美:单链表逆序

让单链表逆序输出
题目:已知单向链表的头结点head,写一个函数把这个链表逆序 (Intel)。这个题目算是考察数据结构的最基础的题目了,下面我们一步步解析这个算法步骤。首先我们创建一个新结点 current p1,并且让它指向首元结点,即 current p1 = L -> next;然后我们创建另外一个新结点 pnext p2,用来保存当前节点的下一个节点,即 pnext p2 = current p1 -> next;

数据结构

《编程之美》3.4:没有头结点的单链表如何删除结点

一个巧妙的思路
题目:假设有一个没有头结点的单链表。一个指针指向此单链表中间的一个节点(非第一个节点, 也非最后一个节点)。请将该节点从单链表中删除。典型的“狸猫换太子”, 若要删除该节点,正常情况下,应该要知道该节点的前面节点的指针,但是由于单链表中没有头结点,所以无法追溯到该节点前面的那个节点,因此,这里采用了“移花接木”的方法。

数据结构

[专题] 结构之美:删除单链表指定位置的数据

单链表删除结点
删除单链表指定的某个结点是单链表的一个基本操作。删除操作大致分为如下三种:删除p所指向结点的后继结点(假设存在),删除p所指向的结点。删除线性表中值为x的数据元素。大致算法思想:删除运算是将表的第i个结点删去。删除结点算法的时间复杂度和插入结点一样,也是O(n)。链表上实现的插入和删除运算,无须移动结点,仅需修改指针。

数据结构

[专题] 结构之美:在单链表指定位置插入数据

单链表插入结点
在单链表指定位置插入数据是单链表的常用操作之一。插入操作大致分为如下三种:在已知P指针所指向的结点后插入一个元素x。在p指针所指向的结点前插入一个元素x。在线性表中值为y的元素插入一个值为x的数据元素。大致算法思想:插入运算是将值为x的新结点插入到表的第i个结点的位置上,即插入到ai-1与ai之间。

C/C++编程语言

typedef与define在用法上的区别

typedef是为类型取了个“别名”
简单来讲:#define只是简单的进行了替换,而typedef则是为类型取了个“别名”。 #define是预处理指令,在编译预处理时进行简单的替换,不作正确性检查,不关含义是否正确照样带入,只有在编译已被展开的源程序时才会发现可能的错误并报错。如果你把#define语句中的数字9 写成字母g 预处理也照样带入。

数据结构

[专题] 结构之美:查找单链表指定位置结点的数据

获取指定结点的数据
查找单链表上指定节点的数据是单链表的一个基本编程要求。假设我们需要查找第i个节点的值,我们可以声明一个节点p,并且让它指向链表的首元节点,同时开始循环。只要循环数j小于i,就让p指向下一个节点。当j=i时跳出循环,这个时候p就到达了我们需要查找的那个节点,p->data就是我们所需要的结果。

数据结构

怎样才算是掌握单链表呢?

单链表的一些基本操作与思路
很多人学习单链表的时候,觉得学得不够深刻,不知道该深入到哪个程度。这里就罗列一下,学了单链表之后至少需要会写的一些对单链表的一些操作。只是简单罗列下,如果你有建议可以补充。首先要声明一个结构体,包含两部分:一是数据域,就是存放数据的。另一个是指针域,指向下一个节点的指针。

数据结构

[专题] 结构之美:单链表的销毁删除

将结点循环free掉
当我们不再使用某个单链表时,我们就要把它销毁,就是要把它在内存中释放掉。单链表的整表删除,先写一些算法思路:声明一节点p和q;将第一个结点赋值给p;循环,将下一结点赋值给q,释放p,将q赋值给p。实现代码如下:……初始条件:顺序线性表L已存在。操作结果:将L重置为空表。

数据结构

[专题] 结构之美:使用尾插法创建单链表

单链表整表创建
头插法建立链表虽然算法简单,但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致,可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上,为此必须增加一个尾指针real,使其始终指向当前链表的尾结点。尾插法从字面意思可以理解为在表的最后插入结点。从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。

数据结构

[专题] 结构之美:使用头插法创建单链表

单链表整表创建
一般有两种常用的方法来建立单链表:头插法与尾插法。头插法从一个空表开始,读取数组a中的字符,生成新结点,将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。比如学校食堂吃饭排了一大队人,你一上来就插到头一个,那么打饭师傅面对的NEXT就是你了,你的下一个就是原来的队头,队头的上一个就是你。

数据结构

单链表的基础知识问与答

从问答中理解单链表的特性
简述数据的逻辑结构和存储结构的区别与联系,它们如何影响算法的设计与实现?若用结点表示某个数据元素,则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见,数据的逻辑结构是反映数据之间的固有关系,而数据的存储结构是数据在计算机中的存储表示。

数据结构

带头结点的单链表的12个基本操作

熟悉带头结点的单链表
前面说了带头结点与不带头结点这两种单链表的一些情况,同时我们知道设置了头结点的单链表可以降低程序复杂性与减少BUG出现率,那么接下来我们来探讨一下关于带头结点的单链表的一些基本操作,这很重要。线性表的单链表存储结构定义如下:……以下是带有头结点的单链表的12个基本操作:……
135 / 139 首页 < Prev 133 134 135 136 137 Next > 尾页 页码: