问题描述
- 判断一个单链表是否有环？
- 如果存在环，如何得到环中节点的数目？
- 如果存在环，如何找到环的入口？
解题思路
- 判断一个单链表是否有环？
我们可以用两个指针来解决这个问题。定义两个指针，同时从链表的头节点出发，一个指针一次走一步， 一个指针一次走两步，如果走的快的指针追上了走得慢的指针，那么链表就包含环。如果走得快的指针走到了链表的末尾都没有追上走的慢的指针，那么链表就不包含环。
- 如果存在环，如何得到环的长度，也就是环中节点的数目？
我们在前面判断一个链表里是否有环的时候用到了一快一慢的两个指针。如果两个指针相遇，表明链表中存在环。两个指针相遇的节点一定是在环中。可以从这个节点出发，一边继续向后移动一边计数，当再次回到这个节点时就可以得到环中节点数了。
- 如果存在环，如何找到环的入口？
如果链表中环有n个节点，在环中相遇的节点为
meetingNode，然后定义两个指针p1和p2指向链表的头节点。指针p1在链表上向前移动n步，然后两个指针以相同的速度移动。当第p2指向环的入口节点时，第一个指针已经围绕着环走了一圈又回到了入口节点，也就是说此时p1==p2。后面会详细解释。
实现
定义节点
private static class ListNode {
private int val;
public ListNode next;
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
@Override
public String toString() {
return val + "";
}
}
1. 判断一个单链表是否有环？
/**
* 存在环，返回相遇的节点，不存在，返回null
*
* @param head
* @return
*/
public static ListNode meetingNode1(ListNode head) {
if (head == null) {
return null;
}
//注释1，为slow指针赋值
ListNode slow = head.next;
if (slow == null) {
//注释1，只有一个节点，没有环，返回null
return null;
}
//注释2，fast指针比slow指针快一步，也就是head.next.next
ListNode fast = slow.next;
while (fast != null && slow != null) {
//注释3，快慢指针相遇，存在环
if (fast == slow) {
return fast;
}
slow = slow.next;
//注释4，fast每次走两步 "没病，走两步" -- 赵本山
fast = fast.next;
if (fast != null) {
fast = fast.next;
}
}
//链表中没有环
return fast;
}
第二个和第三个问题一起解决
/**
* @param head
* @return 返回环的入口节点
*/
public static ListNode loopNode(ListNode head) {
//如果meetingNode不为null，说明链表有环
// 1->2->3->4->5->6
// ^ |
// | |
// +--------+
//比如这个链表，meetingNode可以是3，4，5，6中的任意一个节点
ListNode meetingNode = meetingNode1(head);
if (meetingNode == null) {
return null;
}
/**
* 环中节点的个数
*/
int nodesInLoop = 1;
//注释1
ListNode node1 = meetingNode;
while (node1.next != meetingNode) {
node1 = node1.next;
nodesInLoop++;
}
System.out.println("环的长度是：" + nodesInLoop);
//注释2，将node1赋值为head，然后向前走的长度就是环的长度
node1 = head;
for (int i = 0; i < nodesInLoop; i++) {
node1 = node1.next;
}
//注释3
ListNode node2 = head;
//注释4处
while (node1 != node2) {
node1 = node1.next;
node2 = node2.next;
}
return node1;
}
重点分析
//注释1
ListNode node1 = meetingNode;
while (node1.next != meetingNode) {
node1 = node1.next;
nodesInLoop++;
}
System.out.println("环的长度是：" + nodesInLoop);
注释1处，将环中相遇的节点为meetingNode赋值给node1，然后node1继续向下走，每走一次累加nodesInLoop，当再次回到meetingNode的时候就得到了环的长度，也就是环中节点的数目。
下面分析一下获取环的入口的代码逻辑。我们先回顾一下解题思路。
如果链表中环有n个节点，在环中相遇的节点为meetingNode，然后定义两个指针p1和p2指向链表的头节点。指针p1在链表上先向后移动n步，然后两个指针以相同的速度向后移动。当第p2指向环的入口节点时，第一个指针已经围绕着环走了一圈又回到了环的入口节点，也就是说此时p1==p2。
//注释2，将node1赋值为head，然后向后走的长度就是环的长度
node1 = head;
for (int i = 0; i < nodesInLoop; i++) {
node1 = node1.next;
}
注释2处，我们将node1赋值为head，就代表解题思路中的p1。然后p1向后走nodesInLoop步。
//注释3
ListNode node2 = head;
注释3处，我们将node2赋值为head，就代表解题思路中的p2。
//注释4处
while (node1 != node2) {
node1 = node1.next;
node2 = node2.next;
}
return node1;
注释4处，判断当node1==node2的时候就跳出循环，此时的node1就是环的入口。
原因分析：
假设链表中的节点数为L（我们可以认为链表的长度就是L），链表中的环中的节点数是N，（我们可以认为环的长度就是N）。那么环外面的长度就是（L-N）。也就是从链表head走L-N步就能到达链表环的入口。但是对于一个有环的链表，我们不好计算链表的长度，也就是说我们没法计算出（L-N的具体值）所以我们可以换一种方案实现。
- 将p1节点指向头节点，然后走N步。p1再走（L-N）步就会回到环的入口了。因为p1已经走了N步，p1再走L-N步就会到到链表的末尾，因为链表是有环的，所以链表的末尾就是链表环的入口。
- 将p2节点指向头节点，p2走L-N步就会到达链表环的入口。
- 此时p1==p2，而且指向节点就是链表的入口。
举个例子：
// 1->2->3->4->5->6
// ^ |
// | |
// +--------+
在这个例子中，链表长度我们认为是6（因为链表中有6个节点）。环的长度是4。
- p1赋值为head，然后向后走4步，此时指向的节点是5。
- p2赋值为head，此时指向的节点是1。
- p1，p2同时向前走2步，此时p1指向节点3，p2指向的节点也是3。
- 说明当p1==p2的时候指向的节点就是环的入口。
完整的代码
public class Test23 {
private static class ListNode {
private int val;
public ListNode next;
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
@Override
public String toString() {
return "Node val is " + val + "\n";
}
}
public static void main(String[] args) {
test01();
test02();
test03();
test04();
test05();
}
/**
* 存在环，返回相遇的节点，不存在，返回null
*
* @param head
* @return
*/
public static ListNode meetingNode1(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head.next;
//注释1，只有一个节点，没有环，返回null
if (slow == null) {
return null;
}
//注释2，fast指针比slow指针快一步，也就是head.next.next
ListNode fast = slow.next;
while (fast != null && slow != null) {
//注释3，快慢指针相遇，存在环
if (fast == slow) {
return fast;
}
slow = slow.next;
//注释4，fast每次走两步 "没病，走两步" -- 赵本山
fast = fast.next;
if (fast != null) {
fast = fast.next;
}
}
//链表中没有环
return fast;
}
/**
* @param head
* @return 返回环的入口节点
*/
public static ListNode loopNode(ListNode head) {
//如果meetingNode不为null，说明链表有环
// 1->2->3->4->5->6
// ^ |
// | |
// +--------+
//比如这个链表，meetingNode可以是3，4，5，6中的任意一个节点
ListNode meetingNode = meetingNode1(head);
if (meetingNode == null) {
return null;
}
/**
* 环中节点的个数
*/
int nodesInLoop = 1;
ListNode node1 = meetingNode;
while (node1.next != meetingNode) {
node1 = node1.next;
nodesInLoop++;
}
System.out.println("环的长度是：" + nodesInLoop);
//将node1赋值为head，然后向前走的长度就是环的长度
node1 = head;
for (int i = 0; i < nodesInLoop; i++) {
node1 = node1.next;
}
ListNode node2 = head;
while (node1 != node2) {
node1 = node1.next;
node2 = node2.next;
}
return node1;
}
// 1->2->3->4->5->6
private static void test01() {
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(loopNode(n1));
}
// 1->2->3->4->5->6
// ^ |
// | |
// +--------+
private static void test02() {
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(loopNode(n1));
}
// 1->2->3->4->5->6 <-+
// | |
// +---+
private static void test03() {
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 = n6;
System.out.println(loopNode(n1));
}
// 1->2->3->4->5->6->7
// ^ |
// | |
// +----------+
private static void test04() {
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);
ListNode n7 = new ListNode(7);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = n3;
System.out.println(loopNode(n1));
}
// 1->2->3->4->5->6->7
// ^ |
// | |
// +-------+
private static void test05() {
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);
ListNode n7 = new ListNode(7);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = n4;
System.out.println(loopNode(n1));
}
}
参考链接
网友评论