单链表面试题JAVA

矫情吗；* 2023-05-30 09:06 20阅读 0赞

package linkedlist;
    
    import java.util.Stack;
    
    public class SingleLinkedListDemo {
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub ilove you
    		//String res=new HeroNode(1, "aa", "bb").toString();
    		//System.out.print(res);
    		//进行测试
    		//先创建节点
    		HeroNode heroNode1=new HeroNode(1, "宋江", "及时雨");
    		HeroNode heroNode2=new HeroNode(2, "宋江2", "及时雨2");
    		HeroNode heroNode3=new HeroNode(3, "宋江3", "及时雨3");
    		//创建要给的链表
    		SingleLinkedlist singleLinkedList=new SingleLinkedlist();
    		singleLinkedList.add(heroNode1);
    		singleLinkedList.add(heroNode2);
    		singleLinkedList.add(heroNode3);
    		singleLinkedList.list();
    		/*
    		//测试修改节点的代码
    		HeroNode newHeroNode=new HeroNode(2, "小路", "玉麒麟~~~~");
    		singleLinkedList.update(newHeroNode);
    		System.out.println("修改后的链表输出");
    		singleLinkedList.list();
    		//删除一个节点
    		singleLinkedList.del(3);
    		System.out.println("删除后的链表输出");
    		singleLinkedList.list();
    		//测试一下单链表的节点个数
    		System.out.println(getLength(singleLinkedList.getHead()));
    		//测试一下是否得到了倒数第k个节点
    		HeroNode res=findLastIndexNode(singleLinkedList.getHead(), 1);
    		System.out.println("res="+res);
    		*/
    		//测试单链表的反转
    		System.out.println("原链表输出");
    		singleLinkedList.list();
    		//System.out.println("反转链表");
    		//reverseList(singleLinkedList.getHead());
    		System.out.println("c测试逆序打印链表");
    		reversePrint(singleLinkedList.getHead());
    		//singleLinkedList.list();
    	}
    	//逆序单链表打印
    	//思路  单链表反转再打印 数据结构破坏X
    	//思路2 ：利用栈的数据结构 将各个节点压入到栈中，然后利用栈的先进后出的特点实现逆序打印
    	public static void reversePrint(HeroNode head){
    		if(head.next==null){
    			return;//空链表不能打印
    		}
    		//创建要给一个栈，将各个节点压入
    		Stack<HeroNode> stack=new Stack<HeroNode>();
    		HeroNode cur=head.next;
    		//将链表的所有节点压入栈
    		while(cur!=null){
    			stack.push(cur);
    			cur=cur.next;//cur后移，这样就可以压入下一个节点
    		}
    		//将栈中的节点继续打印 pop出战
    		while(stack.size()>0){
    			System.out.println(stack.pop());
    			
    		}
    	}
    	//单链表反转
    	//思路 1.定义一个节点reversHead=new HeroNode()   
    	//2.从头到尾遍历原来的链表 每遍历一个节点，就将其取出，并放入新的链表的前端
    	//3.原来的链表的head.next=reverseHead.next;
    	public static void reverseList(HeroNode head) {
    		//如果当链表为空，或者只有一个节点，无需反转，直接返回
    		if(head.next==null||head.next.next==null){
    			return;
    		}
    		//定义一个辅助的指针（变量）帮助我们遍历原来的链表
    		HeroNode cur=head.next;
    		HeroNode next=null;//指向当前节点curr的下一个节点
    		HeroNode reverseHead=new HeroNode(0, "", "");
    		//遍历原来的链表，每遍历一个节点，就将其取出，并放入新的链表reverseHead的前端
    		while(cur!=null){
    			next=cur.next;//先暂时保存当前节点的下一个节点，因为后面要用
    			
    			cur.next=reverseHead.next;//将cur的下一节点指向新的链表的最前端（头部）
    			reverseHead.next=cur;//将cur连接到新的链表
    			cur=next;//让cur移动后一次
    		}
    		//将head.next指向reverseHead.next,实现了单链表的反转
    		head.next=reverseHead.next;
    	}
    	
    	//查找单链表中的倒数第k个节点
    	//1编写一个方法，接收head节点，同时接收一个index
    	//2.index表示是倒数第index个节点
    	//3.先把链表从头到尾遍历一下，得到链表额总的长度getlength
    	//4.得到size后，从链表的第一个开始遍历（size-index）个
    	//5.如果找到了，则返回节点，否则返回null
    	public static HeroNode findLastIndexNode(HeroNode head,int index) {
    		//判断链表为空
    		if(head.next==null){
    			return null;
    		}
    		//第一个遍历得到链表的长度（节点个数）
    		int size=getLength(head);
    		//第二次遍历大size-index位置，就是我们倒数的第k个节点
    		//先做一个Index校验heli
    		if(index<=0||index>size){
    			return null;
    		}
    		//定义给辅助变量  for循环定位到倒数Index
    		HeroNode cur=head.next;
    		for(int i=0;i<size-index;i++){
    			cur=cur.next;
    		}
    		return cur;		
    	}
    	//获取单链表的节点的个数方法（如果带头节点的链表，需求不统计头结点
    	//head链表的头结点返回有效节点
    	public static int getLength(HeroNode head){
    		if(head.next==null){
    			return 0;
    		}
    		int length=0;
    		//定义一个辅助变量
    		HeroNode cur=head.next;
    		while(cur!=null){
    			length++;
    			cur=cur.next;//遍历
    			
    		}
    		return length;
    		
    	}
    
    }
     class HeroNode {
    	public int no;
    	public String name;
    	public String nickname;
    	public HeroNode next;// 指向下一个节点
    	// 构造器
    
    	public HeroNode(int no, String name, String nickname) {
    		this.no = no;
    		this.name = name;
    		this.nickname = nickname;
    	}
    	// 重写toString
    	@Override
    	public String toString() {
    		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" +nickname+" ]";
    	}
    
    }
    class SingleLinkedlist{
    	private HeroNode head=new HeroNode(0, "", "");
    	//添加节点到单向链表
    	//当不考虑编号顺序时；
    	//找到当前链表的最后节点‘
    	//将最后这个节点的next指向新的节点
    	
    	public void add(HeroNode heroNode){
    		//因为head节点不能动，因此我们需要一个辅助遍历temp
    		HeroNode temp=head;
    		//遍历链表，找到最后
    		while(true){
    			//找到链表的最后
    			if(temp.next==null){
    				break;
    			}
    			//如果没有找到最后 就temp后移
    			temp=temp.next;
    		}
    		//当退出while循环时，temp就指向了链表的最后
    		temp.next=heroNode;
    		
    	}
    	public HeroNode getHead() {
    		return head;
    	}
    	//第二种添加英雄时的，根据排名将英雄插入到指定的位置
    	//如果这个排名刚添加失败，并给出显示
    	public void addByOrder(HeroNode heroNode){
    		//因为头结点不动，因此我们任然通过辅助指针（变量）来找到一个添加的位置
    		//因为时单链表因此我们的temp是位于添加位置的前一个节点，否则插入不了
    		HeroNode temp=head;
    		boolean flag=false;//标志添加的编号是否存在，默认为false;
    		while(true){
    			if(temp.next==null){
    				break;
    			}
    			if(temp.next.no>heroNode.no){//位置找到，就在temp的后面插入
    				break;
    			}else if(temp.next.no==heroNode.no){
    				flag=true;//说明编号存在
    			}
    			temp=temp.next;
    		}
    		//判断flag的值
    		if(flag){
    			System.out.printf("准备插入的英雄编号%d存在\n",heroNode.no);
    		}else{
    			//插入到链表中temp后面
    			heroNode.next=temp.next;
    			temp.next=heroNode;
    		}
    		
    	}
    	//修改节点信息，根据no编号来修改，即no编号不能改
    	//1.根据newHeroNode的no来修改即可
    	public void update(HeroNode newHeroNode){
    		//判断链表是否为空
    		if(head.next==null){
    			System.out.println("链表为空");
    			return;
    		}
    		//找到需要修改的节点，根据no编号
    		//d定义一个辅助变量
    		HeroNode temp=head.next;
    		boolean flag=false;//表示是否找到该节点
    		while(true){
    			if(temp==null){
    				break;//链表已经结束遍历完
    			}
    			if(temp.no==newHeroNode.no){
    				//找到了
    				flag=true;
    				break;
    			}
    			temp=temp.next;
    		}
    		//根据flag判断要修改的节点
    		if(flag){
    			temp.name=newHeroNode.name;
    			temp.nickname=newHeroNode.nickname;
    		}else{//没有找到
    			System.out.printf("没有找到 编号为%d的节点，不能修改为\n",newHeroNode.no);
    			
    		}
    	}
    	//删除节点
    	//1.head不能动因此我们需要一个辅助节点temp找到待删除节点的前一个节点
    	//2.说明我们在比较时候，是temp.no和需要删除的节点的.no比较
    	public void del(int no) {
    		HeroNode temp=head;
    		boolean flag=false;//标识是否待删除节点的
    		while(true){
    			if(temp.next==null){
    				break;
    			}
    			if(temp.next.no==no){
    				//找到待删除结点额前一个
    				flag=true;
    				break;
    			}
    			temp=temp.next;//temp后移
    			
    		}
    		if (flag) {
    			//可以删除了
    			temp.next=temp.next.next;
    			
    		}else{
    			System.out.printf("要删除的%d节点不存在\n",no);
    		}
    		
    	}
    	
    	//显示链表【遍历】
    	public void list(){
    		//判断链表是否为空
    		if(head.next==null){
    			System.out.print("链表为空");
    			return;
    		}
    		//因为head节点不能动，因此我们需要一个辅助遍历temp
    		HeroNode temp=head;
    		//遍历链表，找到最后
    		while(true){
    			if(temp==null){
    				break;
    			}
    			//输出节点信息
    			System.out.println(temp);
    			//将temp后移
    			temp=temp.next;
    		}
    	}
    
    }
    /*
     * 从单链表种删除一个节点
     * 先找到需要删除这个节点的前一个节点
     * temp.next=temp.next.next;
     * 被删除的节点不会有其他引用指向，会被垃圾回收机制会删
     *
     * 
    */

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1ODg2MA_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1ODg2MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191108194901948.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1ODg2MA==,size_16,color_FFFFFF,t_70