`
sharp-fcc
  • 浏览: 110389 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

归纳链表题的另一类解法

阅读更多
经初步研究发现,所有公司的面试中链表是必考的内容,所以找了些题整理了一下。链表的题型虽然千变万化,很难捉摸,但其中还是有一些共性问题的,在这里选几道简单总结一下。

 

1. 如何找出单链表的中间节点?

你可以先遍历一次,数一下结点个数。然后结点个数除以2再数一遍。这样做是可以的,但这样的解法与本文的主题无关。本文是要介绍“两个变量”的解法。

1) 定义两个指针fast和slow指向链表头;

2) 在循环体中,fast每次向后移动两个结点,slow移动结点;

3) 当fast到达链表尾时,slow正好位于中间位置。

 

 

2.如何找出单链表中倒数第k个节点?

如果是数组就简单了,直接长度除以2取数就可以了。如果是双向链表也行,定义两个指针,一个从头走,一个从尾走,两个相遇点就是中点。但如果是单链表呢,怎么办?



1) 定义两个指针fast和slow指向链表头;

2) 首先,fast向后移动k个结点;

3) 在循环体中,fast和slow每次向后移动一个结点;

4) 当fast到达链表尾时,slow正好位于倒数第k个位置。




3.如何判断单链表中是否有环?



这道题可以用反转法来解决,但按照本文的主题要推荐的是下面这个解法:

1) 定义两个指针fast和slow指向链表头;

2) 在循环体中,fast每次向后移动两个结点,slow每次向后移动一个结点;

3) 如果没有环的话,fast会抵达链表尾,否则fast会追上slow;



4.如何判断两个链表是否交叉?

如果你把两个单链表交叉想成了X形那你就废了。单链表交叉怎么会是X形,应该是Y形才对呀,这下简单了:


1) 定义两个指针a和b分别指向了两个链表头A,B;

2) 遍历A,使a指向尾结点;

3) 遍历B,使b指向尾结点;

4) 如果a==b则交叉,否则不交叉。



5.如何找出两个交叉链表的交叉节点?





两个指针分别指向两个表头,然后依次后移,行么?能相遇在交叉点么?当然不行啦,只有当两个指针到交叉点的距离相同时,依次后移才会在交叉点相遇:

1) 定义两个指针a和b分别指向了两个链表头A,B;

2) 遍历A,得到链表长度La;

3) 遍历B,得到链表长度Lb;

4) 再使指针a和b分别指向了两个链表头A,B;

5) 假设La〉=Lb,使a向后移动La-Lb个结点;

6) 在循环体中,检验a是否等于b,如果相等则返回a;否则a,b后移一个结点;



6. 给定一个单向链表(可能是循环链表)的头指针,如何找出这个链表循环部分的第一个节点?

哪个公司考这么变态的题呀,不想招人就算了,这么找人开涮也太不厚道了。

1) 算法3检验是否有环,如果无环则返回,有环继续;

2) 在算法3停止的位置断开环;

3) 用算法5找出环的第一个结点;

4) 遍历到链表末尾,恢复环。

  

总结:

以上几道题有一个共同的特点,就是定义两个指针变量,并使其形成特定的位置关系,循环移动之后就能得到想要的结果,这就是这类题的固定模式了。也是本文的标题“两个变量”的由来。

1. 两个指针变量形成移动二倍关系,一个移动到尾部时,那么另一个就在中间;

2. 两个指针变量形成相距k的关系,一个移动到尾部时,那么就在倒数k的位置;

3. 两个指针变量形成快慢关系,如果轨迹是圆环,那么快的就能追上慢的;

4. 两个指针变量都移到可能的交叉点之后的对等位置(到交叉点距离相同),如果变成了同一个指针,那么就是相交的;

5. 两个指针变量找到第一个的对等位置(到交叉点距离相同),再平行移动,那么就能在交叉点相遇;

6. 3 + 5
分享到:
评论

相关推荐

    CCFCSP真题 刷题 和真题分析.zip

    2. **数据结构**:包括数组、链表、栈、队列、树(二叉树、平衡树、堆等)、图、哈希表等,理解并能灵活运用各种数据结构是解决问题的关键。 3. **编程语言基础**:C++、Java或Python是常见的考试语言,考生需要...

    ACM题库资料

    同时,通过对比不同解法,学习者可以领略到算法的多样性和优化的可能性,进一步提升自身的编程思维。 四、涵盖的主题与技术 题库中的题目涵盖了如下主题和技术: 1. 数据结构:链表、栈、队列、树、图、哈希表等; ...

    IOI国家集训队论文集1999-2019

    何 林 -《一类称球问题的解法》 侯启明 -《信息论在信息学竞赛中的简单应用》 姜尚仆 -《模线性方程的应用——用数论方法解决整数问题》 金 恺 -《探寻深度优先搜索中的优化技巧——从正方形剖分问题谈起》 雷环...

    2010考研数据结构复习重点归纳.rar

    树结构是数据结构中的一大类,包括二叉树、平衡树(如AVL树和红黑树)、堆(如最大堆和最小堆)等。二叉树是一种每个节点最多有两个子节点的树,广泛应用于搜索和排序;平衡树通过保持左右子树的高度差不超过1,确保...

    猴子选大王

    在计算机科学中,这类问题属于数据结构与算法的范畴,特别是图论和递归算法的应用。 首先,我们来详细解析这个问题的逻辑。假设有一群数量为n的猴子,它们按顺序编号为1到n。每次从第k只猴子开始计数,数到第m只...

    约瑟夫问题(环中有一个做杀手,即每次都跳过)

    在链表实现中,可以快速地删除节点并找到下一个节点;而在数组实现中,可能需要额外的标记来指示已经被排除的人,因为数组无法直接移除元素。 为了优化算法,我们可以考虑使用模运算,这样可以避免计数溢出,同时...

    数据结构第5章1

    代码示例中,`RecurveArray`类定义了一个数组类,包含输入数组、求最大值、求和及求平均值的递归方法。`MaxKey`方法通过递归比较当前元素和前n-1个元素的最大值来找到最大值,`Sum`方法类似,累加n-1个元素后加上...

    北京大学OJ题目详细分类

    本篇文章将基于北京大学在线评测系统(Online Judge,简称OJ)的部分题目进行详细的知识点归纳与解析。北京大学OJ是计算机科学领域内非常知名的平台之一,尤其是对于算法学习者而言,它提供了丰富的编程题目,覆盖了...

    自个网上看到好的算法文章收集和归纳,很是不错!对于你学算法很有帮助,里面资料很多,自己看看,不列了

    8. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图、哈希表等都是算法的基础,理解它们的特性和操作是学习算法的前提。 9. **递归与迭代**:递归是解决问题的一种常用思路,如阶乘...

    Python Algorithms, 2nd Edition

    - **问题规约**:介绍如何将一个复杂问题转化为已知解法的问题,从而简化求解过程。 ##### 五、遍历技巧(Chapter 5: Traversal: The Skeleton Key of Algorithmics) - **树与图的遍历**:探讨深度优先搜索(DFS)...

    java数据结构与算法,

    重载(overload)是在同一类中可以有多个同名但参数列表不同的方法。 - **1.2.3 接口** - **接口定义**:使用interface关键字。 - **实现接口**:使用implements关键字。 - **多接口实现**:一个类可以实现多个...

Global site tag (gtag.js) - Google Analytics