这道题也是面试中必考的一道题。通常面试官让我们手撕出来，并且让我们讲解思路，来一起看看吧！
1.序
首先我们来看一下比较简单的，如何判断链表是否成环。
快慢指针
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow=head,fast=head;//双指针 ：快慢指针
while (fast!=null && fast.next!=null)
{
slow = slow.next;
fast = fast.next.next;
if(slow==fast)
return true;
}
return false;
}
}
HashSet
定义一个HashSet用来存放节点的引用，并将其初始化为空，从链表的头节点开始向后遍历，每遍历到一个节点就判断HashSet中是否有这个节点的引用。如果没有，说明这个节点是第一次访问，还没有形成环，那么将这个节点的引用添加到HashSet中去。<mark>如果在HashSet中找到了同样的节点，那么说明这个节点已经被访问了</mark>，于是就形成了环。
这种方法的时间和空间复杂度都为O(N)。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
public boolean hasCycle(ListNode head) {
//创建集合对象
HashSet<ListNode> set = new HashSet<ListNode>();
//遍历链表
ListNode p = head;
while (p != null){
if (set.contains(p)){
return true;
}else{
set.add(p);
}
p = p.next;
}
return false;
}
}
2.题目
一个链表中包含环，请找出该链表的环的入口结点。
思路 1
可以用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头结点。如果链表中的环有n个结点，指针P1先在链表上向前移动n步，然后两个指针以相同的速度向前移动。 <mark>当第二个指针指向的入口结点时，第一个指针已经围绕着揍了一圈又回到了入口结点</mark>。
以下图为例，指针P1和P2在初始化时都指向链表的头结点。由于环中有4个结点，指针P1先在链表上向前移动4步。接下来两个指针以相同的速度在链表上向前移动，直到它们相遇。它们相遇的结点正好是环的入口结点。
现在，关键问题在于怎么知道环中有几个结点呢？
可以使用快慢指针，一个每次走一步，一个每次走两步。如果两个指针相遇，表明链表中存在环，并且两个指针相遇的结点一定在环中。
随后，我们就从相遇的这个环中结点出发，一边继续向前移动一边计数，当再次回到这个结点时，就可以得到环中结点数目了。
public class EnterNodeInLink {
public ListNode getEnterNode(ListNode head){
//参数校验
if(head == null){
return null;
}
//如果有环，第一个和第二个指针在环中相遇时的节点
ListNode meetingNode = meetingNode(head);
int ringLength = 0;
//环的长度
if(meetingNode != null){
//如果存在环，就求出环的长度
ListNode tempNode = meetingNode;
meetingNode = meetingNode.next;
while(meetingNode != tempNode){
ringLength++;
meetingNode = meetingNode.next;
}
ringLength++;
}else{
//如果不存在环，就返回null
return null;
}
ListNode ahead = head;
//第一个指针
ListNode behind = head;
//第二个指针
while(ringLength > 0){
ahead = ahead.next;
//第一个指针先在链表上向前移动ringLength步
ringLength--;
}
while(ahead != behind){
ahead = ahead.next;
behind = behind.next;
}
return behind;
}
//在链表存在环的情况下，找到一快一慢两个指针相遇的节点
public ListNode meetingNode(ListNode head){
//参数校验
if(head == null){
return null;
}
ListNode behind = head.next;
//后面的指针
//如果只有一个节点直接返回null
if(behind == null){
return null;
}
ListNode ahead = behind.next;
//前面的指针
while(behind != null && ahead != null){
if(behind == ahead){
return ahead;
}
//behind指针在链表上移动一步
behind = behind.next;
//ahead指针在链表上移动两步
ahead = ahead.next;
if(ahead != null){
ahead = ahead.next;
}
}
return null;
}
public static void main(String[] args) {
EnterNodeInLink test = new EnterNodeInLink();
ListNode head = new ListNode();
ListNode temp1 = new ListNode();
ListNode temp2 = new ListNode();
ListNode temp3 = new ListNode();
ListNode temp4 = new ListNode();
ListNode temp5 = new ListNode();
head.value=1;
temp1.value=2;
temp2.value=3;
temp3.value=4;
temp4.value=5;
temp5.value=6;
head.next=temp1;
temp1.next=temp2;
temp2.next=temp3;
temp3.next=temp4;
temp4.next=temp5;
temp5.next=null;
ListNode resultNode = test.getEnterNode(head);
if(resultNode != null){
System.out.println(resultNode.value);
}else{
System.out.println("您输入的参数有误！");
}
}
}
class ListNode{
int value;
ListNode next;
}
<mark>进行优化，是不是感觉以上代码太过于复杂</mark>，
1.假设链表共有a+b个节点,其中链表头部到链表入口有a个节点(不计链表入口节点),链表环有b个节点,
2.fast走的步数是slow步数的2倍，当有环时，fast比slow多走了n个环的长度,即 f = 2 * s f = s + nb
3.两式相减 f = 2 * nb s = nb，可知fast走了2n个环的长度，slow走了n个环的长度。
4.而且我们知道所有走到链表入口节点的步数是 k = a + nb 。因此我们只需要让slow 再走 a ，就可以到达入口处。
5.这个时候依然用双指针法，让另一个指针从链表头部出发，那么它到达入口正好为 a 。
6.因此在环内 fast slow 指针相遇，让fast 充当那个指针就可以，此时它们相遇，返回slow 指针所指向的节点。
时间复杂度O(N)
空间复杂度O(1)
public class hasCycle {
public static void main(String[] args) {
// test1();
//test2();
test3();
}
// 1->2->3->4->5->6 <-+
// | |
// +---+
private static void test3() {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
//ListNode n6 = new ListNode(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n3;
// n6.next = n3;
System.out.println(hasCycle(n1));
}
private static void test2() {
// 1->2->3->4->5->6
// ^ |
// | |
// +--------+
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
ListNode n6 = new ListNode(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n3;
System.out.println(hasCycle(n1));
}
//1->2->3->4->5->6
private static void test1() {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
ListNode n6 = new ListNode(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
System.out.println(hasCycle(n1));
}
public static ListNode hasCycle(ListNode head) {
if(head == null || head.next == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
//首先定义两个指针
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {
fast = head;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
优质文章推荐
1.计算机网络----三次握手四次挥手
2.一篇让你彻底了解http请求报文和响应报文的结构
3.梦想成真-----项目自我介绍
4.一篇让你彻底了解HTTP 的前世今生
5.一篇让你彻底搞定HTTP方法与状态码
6.你们要的设计模式来了
7.震惊！来看《这份程序员面试手册》！！！
8.一字一句教你面试“个人简介”
9.接近30场面试分享
京公网安备 11010502036488号