一、链表简介：
内存.png
链表是由内存中一系列不相连的结构组成，每一个结构均含有表元素和next指针。优点是插入和删除比较方便(不需移动其他元素, 只需改变指针)，缺点是访问效率低，存储空间利用率高。
数组和链表比较：
数组静态分配内存，链表动态分配内存；数组在内存中连续，链表不连续；数组的元素在栈区，链表的元素在堆区；数组的查询效率比链表高；数组的插入和删除数据，需要其余数据移动，而链表只要在节点上插入和删除就可以；数组查询需要索引查询，链表查询需要遍历整个表。
二、链表分类：
单向链表
Snip20170615_7.png
循环链表
Snip20170615_8.png
双向循环链表
Snip20170615_9.png
三、以单向链表演示链表操作
//链表操作：插入，删除，遍历
class Haha {
public static void main(String[] args){
LinkList theList = new LinkList();
theList.insertFirst(22,2);
theList.insertFirst(33,3);
theList.insertFirst(44,4);
theList.insertFirst(55,5);
theList.insertFirst(66,6);
theList.insertFirst(77,7);
theList.displayList();
while (!theList.isEmpty()){
JieDian aLink = theList.deleteFirst();
System.out.print("Deleted ");
aLink.displayJieDian();
theList.displayList();
System.out.println(" ");
}
theList.displayList();
}
}
class JieDian{
int iData;
double dData;
JieDian next;
JieDian(int id,double dd){
iData = id;
dData = dd;
}
public void displayJieDian(){
System.out.println("{"+iData+","+dData+"}");
}
}
class LinkList{
JieDian first;
LinkList(){
first = null;
}
public boolean isEmpty(){
return (first == null);
}
public void insertFirst(int id,double dd){
JieDian newJieDian = new JieDian(id,dd);
newJieDian.next = first;
first = newJieDian;
}
public JieDian deleteFirst(){
JieDian temp = first;
first = first.next;
return temp;
}
public void displayList(){
System.out.println("List(first -->last):");
JieDian current = first;
while(current != null){
current.displayJieDian();
current = current.next;
}
}
}
结果：
Snip20170616_1.png
常见问题：
1.判断一个给定的单链表是否有环？
2.环的入口
3.环的长度
Snip20170619_1.png
Snip20170619_3.png
第一次相遇时：
slow走的长度S=AB+BC
fast走的长度2S=AB+BC+n*R
AB=n*R-BC
求入口：让两个指针同时分别从A、C出发，相遇点就是入口B
求环长：C点相遇之后，指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。
代码：
class Haha {
public static void main(String[] args){
JieDian j1 = new JieDian(11,1);
JieDian j2 = new JieDian(22,2);
JieDian j3 = new JieDian(33,3);
JieDian j4 = new JieDian(44,4);
JieDian j5 = new JieDian(55,5);
JieDian j6 = new JieDian(66,6);
JieDian j7 = new JieDian(77,7);
JieDian j8 = new JieDian(88,8);
JieDian j9 = new JieDian(99,9);
JieDian j10 = new JieDian(110,1);
JieDian j11 = new JieDian(111,1);
j1.next = j2;
j2.next = j3;
j3.next = j4;
j4.next = j5;
j5.next = j6;
j6.next = j7;
j7.next = j8;
j8.next = j9;
j9.next = j10;
j10.next = j11;
j11.next = j5;
//环长
int x = length(hasLoop(j1));
System.out.println(x);
//入口
rukou(j1,hasLoop(j1)).displayJieDian();
}
//入口节点
public static JieDian rukou(JieDian jd1,JieDian jd2){
JieDian a1 = jd1;
JieDian a2 = jd2;
while (true){
a1 = a1.next;
a2 = a2.next;
int d1 = a1.iData;
int d2 = a2.iData;
double t1 = a1.dData;
double t2 = a2.dData;
if(d1 == d2 && t1 == t2){
return a1;
}
}
}
//环长
public static int length(JieDian jd){
JieDian slow = jd;
JieDian fast = jd;
int length = 0;
while(fast != null){
length++;
slow = slow.next;
fast = fast.next.next;
int d1 = slow.iData;
int d2 = fast.iData;
double t1 = slow.dData;
double t2 = fast.dData;
if(d1 == d2 && t1 == t2){
return length;
}
}
return 0;
}
//是否存在环，如果存在，返回相遇的结点
public static JieDian hasLoop(JieDian jd){
JieDian slow = jd;
JieDian fast = jd;
while(fast != null){
slow = slow.next;
fast = fast.next.next;
if(fast == null){
System.out.println("不存在环");
return null;
}
int d1 = slow.iData;
int d2 = fast.iData;
double t1 = slow.dData;
double t2 = fast.dData;
if(d1 == d2 && t1 == t2){
System.out.println("存在环");
return slow;
}
}
return null;
}
}
class JieDian{
int iData;
double dData;
JieDian next;
JieDian(int id,double dd){
iData = id;
dData = dd;
}
public void displayJieDian(){
System.out.println("{"+iData+","+dData+"}");
}
}
运行结果：
Snip20170619_4.png
