单链表之环形链表

    不论在面试或者刷题过程中,很大概率都会遇到环形链表这种类型的题目,例如 leetcode 141. 环形链表 以及 leetcode 142. 环形链表 II 等,本文主要介绍通过快慢指针法来解决此类题型,以供大家参考。

环形链表

 

 环形链表大致样子如下图所示:

 快慢指针法

判断链表是否是环形链表,一般通过快慢指针法

操作步骤

一、分别定义两个均指向头节点的指针(fast/slow);

二、快指针每次走两步,慢指针每次走一步

三、如果链表存在环,则快慢指针一定会在环中相遇

 

如下图示,快慢指针行走的轨迹如下:

faster: 1--->3--->5--->7

slower:1--->2--->3--->4

faster: 7--->5

slower:4--->5

当他们同时到达节点 5 时,完美相遇

 

 举栗1:判断链表是否有环

题目

Show me the Code

 

 

 举例2:求入环的第一个节点

题目

思路

 本题除了需要判断链表是否有环外,如果有环还要求入环的第一个节点,因此是上一个题目的升级版本,还是以快慢指针中举例的那个链表作为示例,下图将描述当链表有环的时候,如何求出入环的第一个节点,见下图示:

已判断链表有环

 

求入环的第一个节点

让慢指针重新指向链表的头节点,并让快慢指针同时每次只走一步

faster:5--->6--->7

slower:1--->2--->3

 

继续走

faster:7--->4

slower:3--->4

当他们同时到达节点 4 时,再次完美相遇

 

 因此,由上面的图可知,当判断链表有环(快慢指针相遇)之后,再让快(或者慢)指针重新指向链表头节点,另外一个指针仍保持指向不变,然后让快/慢指针同时走,且每次只走一步,当他们再次相遇时,此时相遇的节点就是入环的第一个节点

Show me the Code

 

 

相关推荐

发表评论

路人甲

网友评论(0)