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 getFirstCommonNode(Node head1, Node head2) {
if (head1 == null || head == null) {
return null;
}
int length1 = getLength(head1);
int length2 = getLength(head2);
int lengthDif = 0; //两个链表长度的差值
Node longHead;
Node shortHead;
//找出较长的那个链表
if (length1 > length2) {
longHead = head1;
shortHead = head2;
lengthDif = length1 - length2;
} else {
longHead = head2;
shortHead = head1;
lengthDif = length2 - length1;
}
//将较长的那个链表的指针向前走length个距离
for (int i = 0; i < lengthDif; i++) {
longHead = longHead.next;
}
//将两个链表的指针同时向前移动
while (longHead != null && shortHead != null) {
if (longHead == shortHead) { //第一个相同的结点就是相交的第一个结点
return longHead;
}
longHead = longHead.next;
shortHead = shortHead.next;
}
return null;
}
//方法：获取单链表的长度
public int getLength(Node head) {
if (head == null) {
return 0;
}
int length = 0;
Node current = head;
while (current != null) {
length++;
current = current.next;
}
return length;
}
class Node {
//注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
int data; //数据域
Node next;//指针域
public Node(int data) {
this.data = data;
}
}
}
