转载请注明本文出处：http://www.cnblogs.com/Starshot/p/6918569.html
链表的结构是由一个一个节点组成的，所谓链，就是每个节点的头尾连在一起。而单向链表就是：每个节点包含了当前节点的值和下一个节点引用。双向链表就是每个节点包含了当前节点的值和上下两个节点的引用。相对于数组结构，链表的增删效率会更加高。
这边文章主要讲怎么用Java实现一个简单的链表结构：单向无环链表。以及实现一些数据处理的方法。
首先，新建一个节点类（本次例子中的节点值都是字符串类型）：
public class Node {
private String value;
private Node next;
public Node(String value){
this.value=value;
}
public Node(){
}
public String getValue(){
return value;
}
public Node getnext(){
return next;
}
public void setValue(String value){
this.value=value;
}
public void setNext(Node next){
this.next=next;
}
}
然后再建一个链表类：
public class MyLinkedTable {
Node head=new Node();
//向链表中增加值
public boolean add(String str){
Node node=new Node(str);
if(head.getnext()==null){
head.setNext(node);;
return true;
}
Node tmp=head;
while(tmp.getnext()!=null){
tmp=tmp.getnext();
}
tmp.setNext(node);
return true;
}
//已知某个节点，然后删除该节点
public boolean delete(Node node){
Node next=node.getnext();
Node nextAddress=next.getnext();
String nextValue=next.getValue();
node.setNext(nextAddress);
node.setValue(nextValue);
return true;
}
//删除第index个节点，index从1开始
public boolean delete(int index){
if(index>length()||index<1){
return false;
}
int i=1;
Node temp=head.getnext();
while(i<index){
temp=temp.getnext();
i++;
}
Node next=temp.getnext();
Node nextAddress=next.getnext();
String nextValue=next.getValue();
temp.setNext(nextAddress);
temp.setValue(nextValue);
return true;
}
//获得第index个节点的值
public String get(int index){
if(index>length()||index<1){
return null;
}
int i=1;
Node temp=head.getnext();
while(i<index){
temp=temp.getnext();
i++;
}
return temp.getValue();
}
//获取链表里面数据的长度，也就是插入了多少个值。
public int length(){
if(head.getnext()==null){
return 0;
}
int i=1;
Node temp=head.getnext();
while((temp=temp.getnext())!=null){
i++;
}
return i;
}
//反转链表
public void reverseTable(){
Node node1=head.getnext();
if(node1==null){
return;
}
Node preNode=null;
Node curNode=node1;
while(true){
Node origNextNode=curNode.getnext();
curNode.setNext(preNode);
if(origNextNode==null){
head.setNext(curNode);
break;
}
preNode=curNode;
curNode=origNextNode;
}
}
//获取中间链表
public String getMid(){
Node slowPointer=this.head.getnext(),fastPointer=this.head.getnext();
while(fastPointer!=null&&fastPointer.getnext()!=null&&fastPointer.getnext().getnext()!=null){
slowPointer=slowPointer.getnext();
fastPointer=fastPointer.getnext().getnext();
}
return slowPointer.getValue();
}
//删除重复链表
public void deleteDuplicateNode(){
Node nodeCur=head.getnext();
if(nodeCur==null) return;
while(nodeCur.getnext()!=null){
Node lastNode=nodeCur;
Node compareNode=lastNode.getnext();
while(compareNode!=null){
if(nodeCur.getValue().equals(compareNode.getValue())){
lastNode.setNext(compareNode.getnext());
compareNode=compareNode.getnext();
}else{
lastNode=compareNode;
compareNode=compareNode.getnext();
}
}
nodeCur=nodeCur.getnext();
}
}
}
需要说明一下，这个链表结构是以head为起始节点，head指向插入的第一个节点（反转后就是最后一个），head本身的value一直都是空的，它只作为起始节点入口存在，不参与节点的计数，所以链表的节点总数（插入数据总数）是不包括head在内的。
接下来对某些方法进行说明：
1.链表反转
//链表翻转就是把原来的1>2>3>4变成4>3>2>1，所以原来在最前面的节点要变成在最后面，最后面的要变成最前面
//就是head的地址引用要变成最后一个节点的，原来head后的第一个节点的地址引用要由第二的节点变为NULL,原来第二个节点的地址引用要由第三个节点变成第一个节点
//以此类推，一直翻转到最后一个。然后把head的地址引用变成最后一个。
//在这个链表里面，head的位置是一直不变的，它永远是最前面，在head之后的节点才开始翻转。
public void reverseTable(){
Node node1=head.getnext(); if(node1==null){
return;
} Node preNode=null;
Node curNode=node1; while(true){
Node origNextNode=curNode.getnext();
curNode.setNext(preNode);
if(origNextNode==null){
head.setNext(curNode);
break;
}
preNode=curNode;
curNode=origNextNode;
} }
2.获得中间节点：
//通过用快慢指针来找到中间节点，快指针的速度为慢指针的两倍，慢指针一次走一个节点，快指针一次走两个节点，
//当快指针走到尽头时，慢指针刚好为中间值，当快指针走到倒数第二个节点时，慢指针为上中位数。
//fastPointer!=null用来判断链表表内除head外有没有其它节点，fastPointer.getnext()!=null判断是否为最后一个节点，
//fastPointer.getnext().getnext()!=null判断是否为倒数第二个节点。
public String getMid(){ Node slowPointer=this.head.getnext(),fastPointer=this.head.getnext();
while(fastPointer!=null&&fastPointer.getnext()!=null&&fastPointer.getnext().getnext()!=null){
slowPointer=slowPointer.getnext();
fastPointer=fastPointer.getnext().getnext();
} return slowPointer.getValue(); }
3.删除具有相同值的节点（重复节点）：
//删除具有相同值的节点
//基本原理是用第一个节点的值和第二个节点值比较，然后和第三个节点比较，以此类推。此时第一个节点为当前节点nodeCur，第二第三以及之后的节点为比较节点compareNode
//一轮比较完毕后，第二个节点就变成nodeCur，之后那些节点就是compareNode
//如果遇到有相同的值的节点，就将该节点的上个节点的next值为该节点的下个节点：lastNode.setNext(compareNode.getnext())，此时该节点就在链表里失去引用了，就相当于删除了。
//所以需要lastNode引用来保存当前比较节点的上一个节点
public void deleteDuplicateNode(){
Node nodeCur=head.getnext(); if(nodeCur==null) return; while(nodeCur.getnext()!=null){
Node lastNode=nodeCur;
Node compareNode=lastNode.getnext();
while(compareNode!=null){ if(nodeCur.getValue().equals(compareNode.getValue())){
lastNode.setNext(compareNode.getnext());
compareNode=compareNode.getnext();
}else{ lastNode=compareNode;
compareNode=compareNode.getnext();
}
}
nodeCur=nodeCur.getnext();
}
}
写好之后可以测试一下：
public class Test {
public static void main(String[] args) {
MyLinkedTable m=new MyLinkedTable();
m.add("1");
m.add("2");
m.add("3");
m.add("4");
m.add("5");
m.add("6");
for(int i=1;i<=m.length();i++){
System.out.println(i+":"+m.get(i));
}
System.out.println("length:"+m.length());
m.reverseTable();
for(int i=1;i<=m.length();i++){
System.out.println(i+":"+m.get(i));
}
System.out.println("length:"+m.length());
m.delete(2);
for(int i=1;i<=m.length();i++){
System.out.println(i+":"+m.get(i));
}
System.out.println("length:"+m.length());
System.out.println(m.getMid());
}
}
运行输出如下：
1:1
2:2
3:3
4:4
5:5
6:6
length:6
1:6
2:5
3:4
4:3
5:2
6:1
length:6
1:6
2:4
3:3
4:2
5:1
length:5
3
还有测试删除重复节点的：
public class Test2 {
public static void main(String[] args) {
MyLinkedTable m=new MyLinkedTable();
m.add("1");
m.add("2");
m.add("3");
m.add("2");
m.add("2");
m.add("6");
for(int i=1;i<=m.length();i++){
System.out.println(i+":"+m.get(i));
}
System.out.println("length:"+m.length());
m.deleteDuplicateNode();
for(int i=1;i<=m.length();i++){
System.out.println(i+":"+m.get(i));
}
System.out.println("length:"+m.length());
}
}
运行输出：
1:1
2:2
3:3
4:2
5:2
6:6
length:6
1:1
2:2
3:3
4:6
length:4
以上就是用java实现单向无环链表的详细过程和解释，如果不妥之处，欢迎指出。