public class LinkList {
public Node head;
public Node current;
public int size;
//方法：向链表中添加数据
public void add(int data) {
//判断链表为空的时候
if (head == null) {//如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
head = new Node(data);
current = head;
} else {
//创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
current.next = new Node(data);
//把链表的当前索引向后移动一位
current = current.next; //此步操作完成之后，current结点指向新添加的那个结点
}
}
//方法重载：向链表中添加结点
public void add(Node node) {
if (node == null) {
return;
}
if (head == null) {
head = node;
current = head;
} else {
current.next = node;
current = current.next;
}
}
//方法：遍历链表（打印输出链表。方法的参数表示从节点node开始进行遍历
public void print(Node node) {
if (node == null) {
return;
}
current = node;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
//方法：判断单链表是否有环。返回的结点是相遇的那个结点
public Node hasCycle(Node head) {
if (head == null) {
return null;
}
Node first = head;
Node second = head;
while (second != null) {
first = first.next;
second = second.next.next;
if (first == second) { //一旦两个指针相遇，说明链表是有环的
return first; //将相遇的那个结点进行返回
}
}
return null;
}
//方法：有环链表中，获取环的长度。参数node代表的是相遇的那个结点
public int getCycleLength(Node node) {
if (head == null) {
return 0;
}
Node current = node;
int length = 0;
while (current != null) {
current = current.next;
length++;
if (current == node) { //当current结点走到原点的时候
return length;
}
}
return length;
}
//方法：获取环的起始点。参数length表示环的长度
public Node getCycleStart(Node head, int cycleLength) {
if (head == null) {
return null;
}
Node first = head;
Node second = head;
//先让second指针走length步
for (int i = 0; i < cycleLength; i++) {
second = second.next;
}
//然后让first指针和second指针同时各走一步
while (first != null && second != null) {
first = first.next;
second = second.next;
if (first == second) { //如果两个指针相遇了，说明这个结点就是环的起始点
return first;
}
}
return null;
}
class Node {
//注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
int data; //数据域
Node next;//指针域
public Node(int data) {
this.data = data;
}
}
}
