更详细的讲解请参看视频：
如何进入google,算法面试技能全面提升指南
在有关链表的面试算法题中，检测链表是否有环是常见的题目。给定一个链表，要求你判断链表是否存在循环，如果有，给出环的长度，要求算法的时间复杂度是O(N), 空间复杂度是O(1).
如果大家对图论有了解的话，那么就会知道深度优先搜索，在进行深度优先搜索时，每遍历一个节点，算法会给该节点设置一个标志位，当节点被访问后，该标志位设置成true, 因此当搜索过程中，如果发现当前节点的标志位已经设置成true的话，那表明图中含有环。
现在问题是，题目要求空间复杂度是O(1), 也就是我们不能分配多余的空间作为节点的标志位，因此，像深度优先搜索那样通过标志位判断队列中是否含有环的做法是行不通的。本节我们看看，如何在没有标志位的条件下，判断一个队列中是否有环。我们以下图的队列为例子进行说明：
这里写图片描述
上面的队列中，含有一个环，环的长度是6，也就是6个节点形成了一个圆环。
如果队列中含有圆环，那么对队列的遍历会有什么影响呢。试想有一个圆形跑道，甲乙两人同时在跑道的起点，如果甲的速度是乙的两倍，那么当乙跑完半圈时，甲跑完一圈回到起点，乙跑完一圈回到起点时，甲跑完两圈也回到起点，这样的话，甲乙重新在起点相遇。
采用上面的思路，如果我们使用两个指针分别从队列的起点出发，一个指针前进一次遍历1个节点，另一个指针前进一次，遍历2个节点，如果队列中有环，那么我们可以确信，前进若干次之后，两个指针会相遇，于是算法就是让两个指针同时前进，如果两个指针能相遇的话，那么可以断定链表中有环。还是以上图为例，假设两个指针h1, h2同时处于队列头节点，h1前进一次经过一个节点，h2前进一次，经过两个节点，我们用stepCount来统计节点前进的次数，当两个节点前进3次，也就是stepCount= 3 的时候，两个指针同时进入到链表的环中：
这里写图片描述
依照顺时针次序，指针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;
}
System.out.println("null");
}
}
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
也就是说，我们的算法，对于含有环的链表，它能够准确的计算环的长度，对于没有环的链表，它也能准确的判断出该链表没有环，于是返回长度为0，这就证明了，我们的算法理论和实现是正确的，更详细的讲解请参看视频：
如何进入google,算法面试技能全面提升指南
网友评论