欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表的基本操作

程序员文章站 2024-03-05 23:58:07
...
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