数据结构：链表Java实现

ListNode head=null;
	public Link(ListNode n){
		head=n;
	}

public class ListNode {
	ListNode next=null;
	int data;
	public ListNode(int data){
		this.data=data;
	}
}

/**
	 * 链表末尾插入数据
	 * @param d
	 */
	public void addNode(int d){
		ListNode n=new ListNode(d);
		if(this.head==null){
			this.head=n;
		}
		else{
			ListNode tmp=this.head;
			while(tmp.next!=null){
				tmp=tmp.next;
			}
			tmp.next=n;
		}
	}
	
	public void addNode(ListNode n){
		if(this.head==null)this.head=n;
		else{
			ListNode tmp=this.head;
			while(tmp.next!=null){
				tmp=tmp.next;
			}
			tmp.next=n;
		}		
	}
	
	/*
	 * 删除第index个节点
	 */
	public boolean deleteNode(int index){
		int i=1;
		if(index<1||index>length())return false;
		if(index==1){
			this.head=this.head.next;
			return true;
		}		
		ListNode preNode=this.head;
		ListNode curNode=preNode.next;
		while(curNode!=null){
			if(i==index-1){
				preNode.next=curNode.next;
				return true;
			}
			preNode=curNode;
			curNode=curNode.next;
			i++;
		}
		return false;
	}
	
	/*
	 * 返回节点长度
	 */
	public int length(){
		int length=0;
		ListNode tmp=this.head;
		while(tmp!=null){
			length++;
			tmp=tmp.next;
		}
		return length;		
	}
	
	/*
	 * 在不知道头指针的情况下删除指定节点
	 */
	public boolean deleteNode1(ListNode n){
		if(n==null||n.next==null)return false;
		n.data=n.next.data;
		n.next=n.next.next;
		return true;
	}
	
	/*
	 * 打印节点
	 */
	public void printList(){
		ListNode tmp=this.head;
		while(tmp!=null){
			System.out.print(tmp.data+" ");
			tmp=tmp.next;
		}
		System.out.println();
	}
	
	/*
	 * 链表反转
	 */
	public Link ReverseIteratively(){
		ListNode pNode=this.head;
		ListNode pPrev=null;
		Link newLink = null;
		while(pNode!=null){
			ListNode pNext=pNode.next;
			if(pNext==null){
				newLink=new Link(pNode);
			}
			pNode.next=pPrev;
			pPrev=pNode;
			pNode=pNext;
		}
		return newLink;
	}
	
	/*
	 * 查找单链表的中间结点
	 * 采用快慢指针的方式查找单链表的中间节点，快指针一次走两步，慢指针一次走一步，当快指针走完时，慢指针刚好到达中间节点。
	 */
	public ListNode SearchMid(){
		ListNode fast=this.head;
		ListNode low=this.head;
		while(fast!=null&&fast.next!=null&&fast.next.next!=null){
			fast=fast.next.next;
			low=low.next;
		}
		System.out.println(low.data);
		return low;		
	}
	
	/*
	 * 查找倒数第k个节点
	 * 采用两个指针P1,P2，P1先前移K步，然后P1、P2同时移动，当p1移动到尾部时，P2所指位置的元素即倒数第k个元素 。
	 */
	public ListNode findElem(ListNode head, int k){
		if(k<1||k>this.length())return null;
		int index=0;
		ListNode p=head;
		ListNode q=head;
		for(int i=0;i<k;i++){
			q=q.next;
		}
		while(q!=null){
			p=p.next;
			q=q.next;
		}
		System.out.println(p.data);
		return p;		
	}
	
	/*
	 * 对列表进行排序
	 */
	public void SortList(){
		ListNode curNode=this.head;
		ListNode nextNode=null;
		int tmp=0;
		while(curNode.next!=null){
			nextNode=curNode.next;
			while(nextNode!=null){
				if(curNode.data>nextNode.data){
					tmp=curNode.data;
					curNode.data=nextNode.data;
					nextNode.data=tmp;
				}
				nextNode=nextNode.next;
			}
			curNode=curNode.next;
		}
	}
	
	/*
	 * 删除重复节点
	 */
	public void deleteDuplecate(){
		ListNode curNode=this.head;
		ListNode nextNode=null;
		while(curNode.next!=null){
			nextNode=curNode;
			while(nextNode.next!=null){
				if(curNode.data==nextNode.next.data){
					nextNode.next=nextNode.next.next;
				}else
					nextNode=nextNode.next;
			}
			curNode=curNode.next;
		}
	}
	
	/*
	 * 从尾到头输出单链表，采用递归方式
	 */
	public void printListReversely(ListNode node){
		if(node.next!=null){
			printListReversely(node.next);
		}
		System.out.println(node.data);
	}