单链表的基本操作

class ListNode{
	int val;
	ListNode next;
	ListNode(int val){
		this.val=val;
	}
}
public class Test {
	
	
	//链表长度
	public static int length(ListNode head) {
		int length=0;
		ListNode tmp=head;
		while(tmp!=null) {
			length++;
			tmp=tmp.next;
		}
		return length;
	}
	
	//增加节点
	public static void add(ListNode head,int val) {
		ListNode node=new ListNode(val);
		if(head==null) {//头结点为空
			head=node;
			return ;
		}
		ListNode tmp=head;
		while(tmp.next!=null) {//遍历到链表尾部
			tmp=tmp.next;
		}
		tmp.next=node;
	}
	
	//删除链表节点
	public static boolean delete(ListNode head,int index) {
		if(index<1||index>length(head)) {//删除位置不正确
			return false;
		}
		if(index==1) {//若删除头结点
			head=head.next;
			return true;
		}
		int i=2;//从第二个节点开始遍历
		ListNode preNode=head;//前驱节点
		ListNode curNode=preNode.next;//当前节点
		while(curNode!=null) {
			if(i==index) {//若当前位置正好是index
				preNode.next=curNode.next;
				return true;
			}
			preNode=curNode;
			curNode=curNode.next;
			i++;
		}
		return false;
	}
	
	//链表排序
	public static ListNode sort(ListNode head) {
		ListNode nextNode=null;//后继节点
		ListNode curNode=head;//当前节点
		int tmp=0;
		while(curNode.next!=null) {//固定curNode，遍历nextNode，找出比curNode小的nextNode，交换位置
			nextNode=curNode.next;
			while(nextNode!=null) {
				if(curNode.val>nextNode.val) {
					tmp=curNode.val;
					curNode.val=nextNode.val;
					nextNode.val=tmp;
				}
				nextNode=nextNode.next;
			}
			curNode=curNode.next;
		}
		return head;
	}
	
	//打印链表
	public static void print(ListNode head) {
		ListNode tmp=head;
		while(tmp!=null) {
			System.out.print(tmp.val+" ");
			tmp=tmp.next;
		}
		System.out.println();
	}
	
	//判断某元素是否在链表中
	public static boolean inList(ListNode head,int key) {
		ListNode tmp=head;
		while(tmp!=null) {
			if(tmp.val==key)
				return true;
			tmp=tmp.next;
		}
		return false;
	}
	
	//链表的反转
	public static ListNode reverse(ListNode head) {
		ListNode preNode=null;
		ListNode curNode=head;
		while(curNode!=null) {
			ListNode nextNode=curNode.next;
			curNode.next=preNode;
			preNode=curNode;
			curNode=nextNode;
		}
		return preNode;
	}
	
	public static void main(String [] args) {
		ListNode head=new ListNode(1);
		add(head,3);
		add(head,5);
		add(head,4);
		add(head,2);
		System.out.println("排序前：");
		print(head);
		sort(head);
		System.out.println("排序后：");
		print(head);
		delete(head,3);
		System.out.println("删除第3个节点后：");
		print(head);
		System.out.println("判断某元素是否在链表中：");
		System.out.println(inList(head,3));
		System.out.println(inList(head,2));
		System.out.println("链表反转后：");
		print(reverse(head));
	}
}

输出：
排序前：
1 3 5 4 2
排序后：
1 2 3 4 5
删除第3个节点后：
1 2 4 5
判断某元素是否在链表中：
false
true
链表反转后：
5 4 2 1