• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

单链表之环形链表

开发技术 开发技术 3周前 (02-17) 14次浏览

    不论在面试或者刷题过程中,很大概率都会遇到环形链表这种类型的题目,例如 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)