如题，各位大神， 小弟java小菜，黑盒测试出身，现在想转自动化，想学java基础啊，不断的在练习面试题，可是真是见一个卡一个，所以 大神们 能否帮我一下，这个题该什么做啊？？？ 在此谢过啊！
------解决思路----------------------
遍历咯,看能不能指回到当前节点。
------解决思路----------------------
对该链表做索引排序，用==判断，发现相同节点则存在环，退出检查，遇到节点的next域为null则不存在环，退出检查。
------解决思路----------------------
import java.util.Random;
class MyNode {
int iValue;
MyNode next;
MyNode (int value) {
System.out.println("add "+ value);
iValue = value;
next = null;
};
public int getValue () {
return iValue;
}
}
class MyList {
int iNum;
MyNode head = null;
public boolean isListValid ()
{
if (head == null) return true;
MyNode p = head;
int i = 0;
while (p.next != null) {
i++;
MyNode c = head;
for(int j = 0; j < i && c != null; j++) {
if (c == p.next) {
return false;
}
else {
c = c.next;
}
}
p = p.next;
}
return true;
}
void add(int value) {
iNum++;
MyNode p = head;
if (p == null) {
head = new MyNode(value);
return;
}
if (isListValid() == false) {
System.out.println("the list has circul node, could not add node into tail");
return;
}
while (p.next != null)
p = p.next;
p.next = new MyNode(value);
}
private void init (int num) {
int i = num;
if (num <= 0) return;
Random ran = new Random(100);
while (i > 0) {
add(Math.abs(ran.nextInt()));
i--;
}
}
private void dump() {
System.out.println("Begin to dump:");
if (!isListValid()) {
System.out.println("the list has circul node, could not add node into tail");
return;
}
MyNode p = head;
while (p != null) {
System.out.println(p.getValue());
p = p.next;
}
}
public void insertInvalidNode() {
if (iNum <= 1) return;
MyNode tail = head;
int i = 0;
while (tail.next != null) {
tail = tail.next;
}
tail.next = head;
}
MyList(int num) {
iNum = num;
init(num);
dump();
}
}
public class ListTest {
public static void main (String[] args) {
MyList list = new MyList(5);
list.insertInvalidNode();
if (list.isListValid() == false) {
System.out.println("the list has circul node, could not add node into tail");
return;
}
}
}
------解决思路----------------------
用两个指针分别扫描链表，一个指针每次走两步，另一个每次走一步
- 如果相遇，则存在环
- 如果到末尾（NULL），则不存在环。
------解决思路----------------------
用Java SE的LinkedList API又实现了一遍。
import java.util.LinkedList;
import java.util.Random;
public class LinkedListTest {
public static void main (String[] args) {
LinkedList<Integer> list = new LinkedList<Integer>();
Random ran = new Random();
Integer i = new Integer(1);
list.add(Math.abs(ran.nextInt()));
list.add(i);
list.add(i);
System.out.println(list);
if (checkValid(list)) System.out.println("It is valid");
else System.out.println("It is invalid");
}
static public boolean checkValid(LinkedList<Integer> list) {
LinkedList<Integer> list1 = (LinkedList<Integer>) list.clone();
System.out.println(list1);
Integer i;
do {
i = list1.removeFirst();
System.out.println(list1);
if (list1.contains((Object) i))
return false;
} while (i != null);
return true;
}
}
------解决思路----------------------
两种方法：
一、快慢指针；一个指针走两步一个指针走一步，相遇则有环
二、一个指针第n步向前一个，另一个指针第n步向前走n个，若第二个指针遇到第一个指针时<n 则有环
------解决思路----------------------
一步两步 是爪牙 是魔鬼的步伐
------解决思路----------------------
算法的思想是设定两个指针p, q，其中p每次向前移动一步，q每次向前移动两步。那么如果单链表存在环，则p和q相遇；否则q将首先遇到null。
假定单链表的长度为n，并且该单链表是环状的，那么第i次迭代时，p指向元素i mod n，q指向2i mod n。因此当i≡2i(mod n)时，p与q相遇。而i≡2i(mod n) => (2i - i) mod n = 0 => i mod n = 0 => 当i=n时，p与q相遇。这里一个简单的理解是，p和q同时在操场跑步，其中q的速度是p的两倍，当他们两个同时出发时，p跑一圈到达起点，而q此时也刚好跑完两圈到达起点。
那么当p与q起点不同呢？假定第i次迭代时p指向元素i mod n，q指向k+2i mod n，其中0<k<n。
------解决思路----------------------
首尾相连或重叠