java:链表操作

约定不等于承诺〃 2022-08-04 05:12 195阅读 0赞

package com.linkedlist;
    
    import java.util.HashSet;
    
    /*
     * 用java语言实现单链表的操作：
     * 1.节点的定义
     * 2.创建链表，在链表尾插入节点
     * 3.链表的长度
     * 4.遍历链表
     * 5.删除节点
     * 6.插入节点
     * 7.链表的排序
     * 8.链表的反转
     * 9.快速找到链表的中间节点
     * 10.删除链表中的重复元素-把元素存储到Hashset中
     * 11.删除链表中的重复元素-双重循环遍历链表
     * 12.寻找单链表的中间节点
     * */
    
    //1.定义节点类型
    class Node
    {
    	int data;  //数据域
    	Node next;  //下一个节点
    	
    	//构造函数
    	public Node(int data)
    	{
    		this.data = data;
    	}	
    	
    	//覆写hashCodef方法
    	public int hashCode()
    	{
    		return new Integer(data).toString().hashCode();
    	}
    	
    	//覆写equals方法
    	public boolean equals(Object obj)
    	{
    		Node d = (Node)obj;
    		if(this.data == d.data)
    			return true;
    		else
    			return false;	
    	}
    }
    
    
    //链表类
    class MyLinkedList 
    {
    	//定义一个首节点
    	Node head = null;
    	
    	//2.创建链表，向链表尾插入节点
    	public void add(int val)
    	{
    		//创建一个新的节点
    		Node newNode = new Node(val);
    		newNode.next = null;
    		
    		//如果链表为空时
    		if(head == null)
    		{
    			head = newNode;
    		}
    		
    		//如果 链表不为空,新节点添加在链尾
    		else
    		{
    			Node tail = head;
    			while(tail.next != null)
    			{
    				tail = tail.next;  //tail指向链表的最后一个元素
    			}
    					
    			tail.next = newNode;
    		}
    	
    	}//add
    	
    	//3.链表的长度
    	int listLength()
    	{
    		int length = 0;
    		Node d = head;
    		while(d != null)
    		{
    			length ++;
    			d = d.next;
    		}
    		
    		return length;
    	}//listLength
    	
    	//4.遍历链表
    	public void traversrList()
    	{
    		Node d = head;
    		
    		while(d != null)
    		{
    			System.out.print(d.data);
    			d = d.next;
    		}
    		
    		System.out.println();
    		
    	}//traversrList
    	
    	//5.删除节点,删除链表中的第pos个节点
    	public void delete(int pos)
    	{
    		//链表的长度
    		int len = listLength();
    		
    		Node d = head;
    		
    		if(pos < 1 || pos >len)
    		{
    			System.out.println("pos位置错误！");
    			return;
    		}
    		else
    		{
    			//如果是第一个节点，删除首节点
    			if(pos == 1)
    			{
    				head = head.next;
    			}
    			
    			//如果不是第一个节点，需要找到第pos-1节点		
    			else
    			{
    				int count = 0;
    				while(d != null)
    				{
    					count ++;
    					if(count == pos - 1)
    					{
    						//d为第pos-1个节点，删除d.next
    						d.next = d.next.next;
    					}
    					d = d.next;
    				}
    			}//else
    			
    		}//else
    		
    	}//delete
    	
    	// 6.插入节点,在第pos位置前，插入元素val
    	public void insert(int pos, int val)
    	{
    		Node d = head;
    		int len = listLength();  //链表长度
    		Node newNode = new Node(val);//新节点
    		newNode.next = null;
    		
    		if(pos < 1 || pos > len + 1)
    		{
    			System.out.println("插入位置错误!");
    			return;
    		}
    		else
    		{
    			//插在首节点位置
    			if(pos == 1)
    			{
    				newNode.next = head.next;
    				head = newNode;
    			}
    			
    			//插在其他位置前,需要获取pos-1位置上的节点
    			else
    			{
    				int count = 0;
    				while(d != null)
    				{
    					count ++;
    					if(count == pos - 1)
    					{
    						//d为第pos-1个节点,newNode插在d后面
    						newNode.next = d.next;
    						d.next = newNode;	
    					}
    					d = d.next;
    				}
    				
    			}
    		}
    		
    	}//insert
    	
    	//7.链表的排序,选择排序
    	public void sort()
    	{		
    		Node p = head;
    		Node q = null;
    		
    		while(p != null)
    		{
    			q = p.next;
    			while(q != null)  //每个节点和后面的元素比较
    			{
    				if(p.data < q.data)
    				{
    					int tmp = p.data;
    					p.data = q.data;
    					q.data = tmp;
    				}
    				
    				q = q.next;
    			}
    			
    			p = p.next;
    		}
    			
    	}//sort
    	
    	//8.链表的反转。破坏了原链表
    	public void reverse()
    	{
    		Node d = head;
    		Node reverse = null;  //反转链表的首结点
    		Node tail;
    		
    		 while(d != null)
    		 {
    			 tail = reverse;
    			 reverse = d;
    			 d = d.next;
    			 reverse.next = tail;
    		 }
    		 
    		head = reverse;
    	}//reverse
    	
    	//9.快速找到链表的中间节点
    	public void findMid()
    	{
    		Node k, m;
    		k = m = head;
    		
    		//快指针到链尾
    		while(k != null && k.next != null && k.next.next != null)  
    		{
    			k = k.next.next;  //快指针每次移动两步
    			m = m.next;  //慢指针每次移动一步
    		}
    		
    		System.out.println("中间节点为：" + m.data);
    	}
    	
    	//10.判断链表是否是循环链表
    	public void isCircle()
    	{
    		Node k, m;
    		k = m = head;
    		boolean flag = false;
    		
    		//快指针到链尾
    		while(k != null && k.next != null && k.next.next != null)
    		{
    			k = k.next.next;  //快指针每次移动两步
    			m = m.next;  //慢指针每次移动一步
    			
    			if(k == m)
    			{
    				flag = true;  //两指针指向同一元素，则有环
    			}		
    		}
    		
    		System.out.println("有环 ：" +flag);
    	}
    	
    	//11.删除链表中的重复元素-把元素存储到Hashset中
    	public void noAgain_hashset()
    	{
    		//定义HashSet集合
    		HashSet<Integer> hs = new HashSet<Integer>();
    		
    		Node d = head;
    		while(d != null)
    		{
    			if(!hs.contains(d.data))
    				hs.add(d.data);   //把不重复元素装入HastSet集合中
    			d = d.next;
    		}
    		
    		System.out.println(hs);
    	}
    	
    	//12.删除链表中的重复元素-双重循环遍历链表
    	//链表前面的元素和后面的每个元素相互比较，删除重复的元素
    	public void noAgain_dul()
    	{
    		Node p = head;
    		while(p != null)
    		{
    			Node q = p;
    			while(q.next != null)
    			{
    				if(p.data == q.next.data)
    				{
    					q.next = q.next.next;  //删除重复元素q.next
    				}
    				
    				q = q.next;
    			}
    			p = p.next;
    		}
    		
    		traversrList();
    	}
    	
    }
    
    public class TestLinkedList
    {
    	public static void main(String[] args)
    	{
    		MyLinkedList list = new MyLinkedList();
    		
    		for(int i = 0; i < 5; i++)
    		{
    			list.add(i);
    		}
    		
    		int length = list.listLength();	
    		System.out.println("len = " +length);
    		
    		System.out.print("遍历链表:");
    		list.traversrList();
    		
    		System.out.print("删除第3个元素:");
    		list.delete(3);
    		list.traversrList();
    		
    		System.out.print("在第5的位置上插入0:");
    		list.insert(5, 0);
    		list.traversrList();
    		
    		System.out.print("链表元素排序:");
    		list.sort();
    		list.traversrList();
    		
    		System.out.print("链表元素反转:");
    		list.reverse();
    		list.traversrList();
    		
    		//System.out.print("链表元素去重，存入HashSet:");
    		//list.noAgain_hashset();
    		
    		System.out.print("双重遍历去重:");
    		list.noAgain_dul();
    		
    		list.findMid();
    		
    		list.isCircle();
    		
    	}
    }

/\*

len = 5  
遍历链表:01234  
删除第3个元素:0134  
在第5的位置上插入0:01340  
链表元素排序:43100  
链表元素反转:00134  
链表元素去重，存入HashSet:\[0, 1, 3, 4\]  
双重遍历去重:0134  
中间节点为：1  
有环 ：false

\*/