在有关链表的面试算法题中，检测链表是否有环是常见的题目。
给定一个链表，要求你判断链表是否存在循环，如果有，给出环的长度，要求算法的时间复杂度是O(N), 空间复杂度是O(1).
方案1 : 深度优先搜索
在进行深度优先搜索时，每遍历一个节点，算法会给该节点设置一个标志位，当节点被访问后，该标志位设置成true, 因此当搜索过程中，如果发现当前节点的标志位已经设置成true的话，那表明图中含有环。
image.png
含有一个环，环的长度是6，也就是6个节点形成了一个圆环
如果队列中含有圆环，那么对队列的遍历会有什么影响呢。试想有一个圆形跑道，甲乙两人同时在跑道的起点，如果甲的速度是乙的两倍，那么当乙跑完半圈时，甲跑完一圈回到起点，乙跑完一圈回到起点时，甲跑完两圈也回到起点，这样的话，甲乙重新在起点相遇。
采用上面的思路，如果我们使用两个指针分别从队列的起点出发，一个指针前进一次遍历1个节点，另一个指针前进一次，遍历2个节点，如果队列中有环，那么我们可以确信，前进若干次之后，两个指针会相遇，于是算法就是让两个指针同时前进，如果两个指针能相遇的话，那么可以断定链表中有环。还是以上图为例，假设两个指针h1, h2同时处于队列头节点，h1前进一次经过一个节点，h2前进一次，经过两个节点，我们用stepCount来统计节点前进的次数，当两个节点前进3次，也就是stepCount= 3 的时候，两个指针同时进入到链表的环中
image.png
依照顺时针次序，指针h2与h1间的距离就是2，我们用d来表示，如果h2要追上h1的话，也就是说，前进指定次数后，h2和h1重合，那么h2经历过的节点数，等于h1经过的节点数加上环的长度，再加上当前距离d,如果用circleLength来表示环的长度，那么以下的公式成立：
2 * stepCount - (1stepCount + d) = kcircleLength
k是任意整数，当k = 1 时，两个指针第一次相遇，当k = 2时两个指针第二次相遇，以此类推。由此，如果我们让两个指针不停的前进，那么两个指针将不停的相遇。
假设使得两指针第一次相遇需要前进的次数用t1来表示，于是有：
2t1 - (t1 + d ) = 1circleLength (1)
如果两指针第二次相遇需要前进的次数用t2来表示，于是有：
2t2 - (t2 + d) = 2circleLenth (2)
用(2) 减去 (1) 有：
t2 - t1 = circleLength
也就是说，只要我们记录第一次相遇时前进的次数，还有第2次相遇时前进的总次数，把两个次数相减，就能得到队列中，环的长度了。
具体代码实现如下：
public class ListUtility {
private Node tail;
Node createList(int nodeNum) {
if (nodeNum <= 0) {
return null;
}
Node head = null;
int val = 0;
Node node = null;
while (nodeNum > 0) {
if (head == null) {
head = new Node();
head.val = val;
node = head;
tail = head;
} else {
node.next = new Node();
node = node.next;
node.val = val;
node.next = null;
tail = node;
}
val++;
nodeNum--;
}
return head;
}
public Node createCycleList(int totalNodeNum, int circleNodeNum) {
if (totalNodeNum < circleNodeNum) {
return null;
}
Node head = createList(totalNodeNum);
Node temp = head;
int stepCount = totalNodeNum - circleNodeNum;
while (stepCount > 0) {
temp = temp.next;
stepCount--;
}
tail.next = temp;
return head;
}
public void printList(Node head) {
while (head != null && head.visited == false) {
System.out.print(head.val + " -> ");
head.visited = true;
head = head.next;
}
}
}
createCycleList用于构造给定环长度的链表，例如要构造图示例子的链表只要调用createCycleList(10, 6)就可以了。
public class CircleList {
private Node stepOne;
private Node stepTwo;
private int stepCount = 0; //移动的步数
private int visitCount = 0; //相遇的次数
int lenOfFirstVisit = 0; //第一次相遇移动的步数
int lenOfSecondVisit = 0; //第二次相遇移动的步数
public int getCircleLength(Node head) {
stepOne = head;
stepTwo = head;
lenOfFirstVisit = 0;
lenOfSecondVisit = 0;
do {
//链表结束 没有环
if ( goOneStep() == false || goTwoStep() == false) {
break;
}
stepCount++;
//链表有环
if (stepOne == stepTwo) {
visitCount++;
if (visitCount == 1) {
lenOfFirstVisit = stepCount;
}
if (visitCount == 2) {
lenOfSecondVisit = stepCount;
}
}
} while(visitCount < 2);
return lenOfSecondVisit - lenOfFirstVisit;
}
private boolean goOneStep() {
if (stepOne == null || stepOne.next == null) {
return false;
}
stepOne = stepOne.next;
return true;
}
private boolean goTwoStep() {
if (stepTwo == null || stepTwo.next == null || stepTwo.next.next == null) {
return false;
}
stepTwo = stepTwo.next.next;
return true;
}
}
getCircleLength（）用于检验给定的链表是否含有环，如果有的话，返回链表环的长度，也就是环中有几个节点，如果输入给定图示链表，那么返回的值是6.它的算法跟我们前面描述的一样，首先使用两个指针stepOne, stepTwo先指向链表的头节点，stepCount用来记录前进的次数，stepOne一次前进遍历一个节点，stepTwo前进一次遍历两个节点。在do…while 循环中，分别让两个指针同时前进，直到两个指针相遇，或者某个指针指向空元素，也就是null为止，第一次相遇时，使用变量lenOfFirstVisit记录前进的次数，第二次相遇时，使用变量lenOfSecondVisit来记录，根据上面的算法推论，两次相遇时前进次数的差值，就是队列中环的长度。
在算法中，由于我们没有分配任何新的空间，所以算法的复杂度为O(1), 在遍历过程中，只要两个指针相遇第二次，那么算法离开终止，这样的话，如果队列中的节点不在圆环中的话，那么它只会被两个指针遍历一次，如果在圆环中，那么节点最多被两个指针遍历两次，因此算法的时间复杂度是O(N).
我们看看算法的运行结果：
public class LinkList {
public static void main(String[] args) {
ListUtility util = new ListUtility();
Node head = util.createCycleList(10, 6);
CircleList cl = new CircleList();
int circleLen = cl.getCircleLength(head);
System.out.println("length of list circle is: " + circleLen);
head = util.createList(10);
circleLen = cl.getCircleLength(head);
System.out.println("length of list circle is: " + circleLen);
}
}
我们先构造一个长度为10，同时含有6个节点的环的链表，然后使用算法计算环的长度，接着再构造一个长度为10， 但是没有环的链表，然后再计算这个链表环的长度，最后运行结果如下：
length of list circle is: 6
length of list circle is: 0
原文链接：https://blog.csdn.net/tyler_download/article/details/53691695
网友评论