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

关于单链表的一些面试题--Java数据结构

程序员文章站 2023-03-07 23:40:04
获取单链表的有效结点的个数这个相对比较容易,定义一个计数器 i,一个辅助遍历的变量temp,对单链表进行遍历,当temp不等于null时,i++代码如下://获取单链表的有效结点个数 (如果是带头结点的链表,不统计头结点)public static int getlength(HeroNode head) {if(head.next==null) {return 0;}int i=0;HeroNode temp = head.next;//定义辅助变量,没有统计...

获取单链表的有效结点的个数
这个相对比较容易,定义一个计数器 i,一个辅助遍历的变量temp,对单链表进行遍历,当temp不等于null时,i++
代码如下:

	//获取单链表的有效结点个数  (如果是带头结点的链表,不统计头结点)
	public static int getlength(HeroNode head) {
		if(head.next==null) {
			return 0;
		}
		int i=0;
		HeroNode temp = head.next;//定义辅助变量,没有统计头结点
		while(temp!=null) {
			i++;
			
			temp=temp.next;
		}
		return i;
	}

查找单链表倒数第k个结点

  1. 建立一个方法传入两个参数,分别是头结点以及k
  2. 首先遍历链表得到链表的长度n
  3. 接着再次遍历链表,当i=(n-k)时,即找到了目标结点,返回
    代码如下:
	//查找单链表中倒数第k个结点
	public static HeroNode getnode(int k,HeroNode head) {
		if(head.next==null) {
			return null;
		}
		int n =getlength(head);//得到链表的长度
		if(k<=0||k>n) {
			return null;
		}
		HeroNode temp = head.next;
		int i=0;
		while(temp!=null) {
			i++;
			temp=temp.next;
			if(i==(n-k)) {
				break;
			}
		
		}
		return temp;
		
	}

对单链表进行反转

  1. 定义一个新的链表头结点reverseList
  2. 定义一个用于遍历的cur,以及一个用于保存当前结点的下一结点的next
  3. 开始遍历原来的链表
  4. 先把当前结点的下一结点保存起来
  5. 接着把当前结点的next指向新的链表的最前端
  6. 再把当前结点cur加入到新的链表
  7. 另cur等于先前保存的结点
  8. 把原来链表的头结点指向新链表的第一个结点

关于单链表的一些面试题--Java数据结构
代码如下:

	//将单链表进行反转
	public static void reverseList(HeroNode head) {
		//如果当前链表为空或只有一个结点,那么不用反转,直接返回
		if(head.next==null||head.next.next==null) {
			return;
		}
		HeroNode cur = head.next;
		HeroNode next = null;//指向当前结点的下一个结点、
		HeroNode reverseHead = new HeroNode(0,"","");
		//遍历原来的链表,每遍历一个节点,将其取出放在新链表reverseHead的最前端
		while(cur!=null) {
			next = cur.next;//先暂时保存当前结点的下一结点,留在后面使用
			cur.next=reverseHead.next;//将cur的next指向新的链表的最前端
			reverseHead.next=cur;//把cur加在新链表上
			cur = next;
		}
		head.next=reverseHead.next;
	}

将链表逆序打印
逆序打印我们其实可以直接调用上面的方法,但有一个问题:上面的方法改变了数据结构,如果链表内容庞大时,则会花费较长时间。因此,这时就可以用到了栈。

  1. 把链表内容加入到栈中
  2. 对栈进行遍历,出栈
  3. 打印
    代码如下:
	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());
		}
	}

因为这些题是在上篇的代码基础上进行的,所以这里就不在说总的代码了。
大家有兴趣可以看上篇单链表的介绍https://blog.csdn.net/LanceHang/article/details/107125610

本文地址:https://blog.csdn.net/LanceHang/article/details/107162425