数据结构：单链表（水浒传英雄操作为例）+单链表面试题

2024-02-21 17:44:10

目录

 

用单链表来实现简单的增删改

面试题

求单链表中有效节点个数

 查找单链表中的倒数第k个节点

单链表的反转（有点难度）

 从尾到头（逆序）打印单链表【要求方式1.反向遍历 2.Stack栈】

合并两个有序的单链表，合并之后的链表依然是有序的

  1. 链表是有序的列表，是以节点的方式来存储，是链式存储。链表的各个节点不一定是连续存放
  2. 每个节点包含data域和next域（指向下一个节点）
  3. 无论是删除还是添加，都要找到待处理节点的前一个节点
  4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
  5. 头节点不存放具体的数据，作用就是表示单链表的头

用单链表来实现简单的增删改

public class SingleLinkedListDemo {

	public static void main(String[] args) {
		HeroNode h1=new HeroNode(1,"宋江","及时雨");
		HeroNode h2=new HeroNode(2,"卢俊义","玉麒麟");
		HeroNode h3=new HeroNode(3,"吴用","智多星");
		HeroNode h4=new HeroNode(4,"林冲","豹子头");
		SingleLinkedList sl=new SingleLinkedList();
//System.out.println("不考虑英雄编号顺序添加的测试");
//		sl.add(h1);
//		sl.add(h2);
//		sl.add(h3);
//		sl.add(h4);
//		sl.list();
		System.out.println("考虑英雄编号顺序添加的测试");
		sl.addByOrder(h1);
		sl.addByOrder(h4);
		sl.addByOrder(h2);
		sl.addByOrder(h3);
//		sl.addByOrder(h3);
//		sl.list();
		HeroNode newh2=new HeroNode(2,"小卢","玉麒麟~~");
		sl.update(newh2);
		sl.del(1);
		sl.del(2);
		sl.del(3);
		sl.del(4);
		sl.list();
		
	}

}
//定义一个SingleLinkedList来管理我们的英雄
class SingleLinkedList{
	//先初始化一个头节点，头节点不要动,不存在具体数据
	private HeroNode head=new HeroNode(0, "", "");
	//添加节点到单向链表
	public void add(HeroNode heronode) {
		//因为head节点不能动，因此我们需要一个辅助变量temp
		HeroNode temp=head;//temp相当于指针
		while(true) {
			//找到链表的最后
			if(temp.next==null) {
				break;
			}
			//如果没有找到最后，就将temp后移
			temp=temp.next;
		}
		//当退出while循环时，temp就指向了链表的最后
		temp.next=heronode;
	}
	public void addByOrder(HeroNode heronode) {
		//因为head节点不能动，因此我们需要一个辅助指针temp来帮助找到添加位置
		//因为是单链表，因为我们找的temp是位于添加位置的前一个节点！！！否则添加不了
		HeroNode temp=head;
		boolean flag=false;//标志添加的编号是否存在，默认为false
		while(true) {
			if(temp.next==null) {//说明temp已经到链表的最后
				break;
			}
			if(temp.next.no>heronode.no) {//位置找到，就在temp的后面
				break;
			}else if(temp.next.no==heronode.no){//说明希望 添加的编号已经存在
				flag=true;
				break;
			}
			temp=temp.next;
		}
		if(flag==true) {
			System.out.printf("准备插入的英雄编号%d已经存在，不能加入\n",heronode.no);
		}else {
			heronode.next=temp.next;
			temp.next=heronode;
		}
	}
	//修改节点的信息，根据no编号来修改，即no编号不能改
	public void update(HeroNode heronode) {
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}
		HeroNode temp=head.next;
		boolean flag=false;
		while(true) {
			if(temp==null) {
				break;//已经遍历完
			}
			if(temp.no==heronode.no) {
				flag=true;
				break;
			}
			temp=temp.next;
		}
		if(flag==true) {
			temp.name=heronode.name;
			temp.nickName=heronode.nickName;
		}else {
			System.out.printf("没有找到编号等于%d的节点\n",heronode.no);
		}
	}
	//删除节点
	public void del(int n) {
		HeroNode temp=head;
		boolean flag=false;
		while(true) {
			if(temp.next==null) {
				break;
			}
			if(temp.next.no==n) {
				flag=true;
				break;
			}
			temp=temp.next;
		}
		if(flag==true) {
			temp.next=temp.next.next;
		}else {
			System.out.printf("要删除的%d节点不存在\n",n);
		}
	}
	//显示链表[遍历]
	public void list() {
		//判断是否为空
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}
		//因为head节点不能动，因此我们需要一个辅助变量temp
		HeroNode temp=head.next;
		while(true) {
			//是否到链表的最后
			if(temp==null) {
				break;
			}
			System.out.println(temp);
			//将temp后移！！！
			temp=temp.next;
			
		}
	}
}
//先定义一个HeroNode,每个HeroNode对象就是一个节点
class HeroNode{
	public int no;//英雄编号,按照编号顺序添加
	//思路：①首先找到新添加节点的位置，通过辅助指针②新的节点的.next=temp.next③将temp.next=新的节点
	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方法
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName+"]" ;
	}
	
}

面试题

  • 求单链表中有效节点个数

主类中添加方法

//方法：获取单链表的有效个数（如果是带头节点的链表需要不统计头节点）
		public static int getLen(HeroNode head){
			//head是头节点，返回有效节点的个数
			if(head.next==null) {
				return 0;
			}
			int length=0;
			HeroNode cur=head.next;
			while (cur!=null) {
				length++;
				cur=cur.next;
			}
			return length;
		}

在 SingleLinkedList类中添加方法，返回头节点

public HeroNode getHead() {
		return head;
	}

  •  查找单链表中的倒数第k个节点

 ①编写一个方法，接收head节点，同时接收一个index

②index表示的是倒数第index个节点

③先把链表从头到尾遍历得到链表的总的长度getLen

④得到size后我们从链表的第一个开始遍历（size-index）个

public static HeroNode findLastIndexNode(HeroNode head,int index) {
			if(head.next==null)
				return null;
			int size=getLen(head);
			if(index<=0||index>size)
				return null;
			HeroNode temp=head.next;
			for(int i=0;i<size-index;i++) {
				temp=temp.next;
			}
			return temp;
		}

  • 单链表的反转（有点难度）

 思路：①先定义一个节点reverseHead=new HeroNode();

②从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前边(新链表头节点后)

③原来的链表的head.next=reverseHead.next

public static void reverseList(HeroNode head) {
			//如果当前链表为空或者只有一个节点，就无需反转
			if(head.next==null ||head.next.next==null) {
				return;
			}
			//辅助指针，帮助遍历原来链表
			HeroNode temp=head.next;
			HeroNode next=null;//指向当前节点的下一个节点
			HeroNode reverseHead =new HeroNode(0, null, null);
			//遍历原来的链表
			while(temp!=null) {
				next=temp.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
				temp.next=reverseHead.next;//将temp的下一个节点指向新的链表的最前端
				reverseHead.next=temp;//将temp连接到新的链表上
				temp=next;
			}
			//将Head.next指向reverseHead.next,实现单链表的反转
			head.next=reverseHead.next;
		}

 数据结构：单链表（水浒传英雄操作为例）+单链表面试题

 从尾到头（逆序）打印单链表【要求方式1.反向遍历 2.Stack栈】

 方式1：先将单链表进行反转操作，然后再遍历即可：这样做的问题是会破坏原来的单链表的结构，不建议这样操作

方式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;//这样就可以压下一个节点
			}
			while(stack.size()>0) {
				System.out.println(stack.pop());
			}
		}

合并两个有序的单链表，合并之后的链表依然是有序的

上一篇：二叉树实现


下一篇：Java数据结构与算法--链表(Linked List)