signed

QiShunwang

“诚信为本、客户至上”

JAVA数据结构与算法——单链表面试题(新浪、百度、腾讯)

2020/8/19 20:53:53   来源:

单链表的常见面试题

  1. 求单链表中有效节点的个数
  2. 查找单链表中倒数第k个节点(新浪)
  3. 单链表的反转(腾讯)
  4. 从尾到头打印单链表(百度,要求方式一:反向遍历。方式二:stack栈)

例题1:求有效节点个数

思路:

  •     方法:获取有效节点 的个数(如果是带头结点的链表,需要不统计头结点)
  •     head是头结点,length是有效节点个数

关键代码实现 :

	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;
	}

例题2:查找单链表中倒数第K个节点

思路:

  • 编写一个方法,接受head节点,同时接收一个index
  • index表示倒数第index个节点
  • 先把链表从头至尾遍历,得到链表总长度getLength
  • 得到size后,我们从链表第一个开始遍历(size-index)个
  • 如果找到了,就返回该节点,否则返回null

关键代码实现:

public static HeroNode findLastIndexNode(HeroNode head, int index) {
		// 判空:链表为空,返回null
		if (head.next == null) {
			return null;
		}
		// 第一次遍历:获取链表长度
		int size = getLength(head);
		// 第二次遍历:(size-index)就是我们倒数第index个节点

		// 数据校验
		if (index <= 0 || index > size) {
			return null;
		}
		// 辅助变量
		HeroNode cur = head.next;

		// for循环定位
		for (int i = 0; i < size - index; i++) {
			cur = cur.next;
		}
		return cur;

	}

例题3:单链表的反转

思路:(注:反转节点,不单单是数据)

  • 先定义一个新节点(reverseHead = new HeroNode())
  • 从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并且放在新链表的最前端
  • 原来的链表的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;// 指向当前节点[cur]的下一个节点
		HeroNode reverseHead = new HeroNode(0, "", "");// 新节点
		// 遍历原来的链表
		while (cur != null) {
			next = cur.next;// 暂时保存当前节点的下一个节点
			cur.next = reverseHead.next;// 将cur的下一个节点指向新的链表的头部节点
			reverseHead.next = cur;//将cur链接到新的链表上
			cur = next;// 后移
		}
		// 将head.next指向reversHead.next,实现反转
		head.next = reverseHead.next;

	}

例题4:从尾到头打印单链表

思路:

方式1:先将单链表进行反转,在遍历,如例题3,但是不建议

方式2:可以利用“栈”,将各个节点压入到栈中,然后利用栈的先进后出的特点,就实现了逆序打印的效果

栈知识补充:先入后出

测试代码(栈)

package com.jun._3_linkedlist;

import java.util.Stack;

/**
 * 测试栈的使用
 * @author jun
 *
 */
public class Test_Stack {

	public static void main(String[] args) {
		Stack<String> stack = new Stack();
		//入栈
		stack.add("jack");
		stack.add("tom");
		stack.add("smith");
		//出栈
		while(stack.size()>0) {
			System.out.println(stack.pop());
		}
	}

}

栈输出 :

smith
tom
jack

代码实现:

	// 逆序打印
	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后移,压入下一个节点
		}
		// 遍历栈中节点
		while (stack.size() > 0) {
			System.out.println(stack.pop());// 先入后出
		}

	}

 

附完整代码

package com.jun._3_linkedlist;

import java.util.Stack;

/**
 * 通过单链表来管理英雄人物
 * 
 * @author jun
 *
 */
public class SingleLinkedListDemo {
	public static void main(String[] args) {

		// 创建节点
		HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
		HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
		HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
		HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

		// 创建链表
		SingleLinkedList singleLinkedList = new SingleLinkedList();

		// 按照方式一加入:
//		singleLinkedList.add(hero1);
//		singleLinkedList.add(hero2);
//		singleLinkedList.add(hero3);
//		singleLinkedList.add(hero4);
		// 按照方式二加入:
		singleLinkedList.add2(hero1);
		singleLinkedList.add2(hero4);
		singleLinkedList.add2(hero2);
		singleLinkedList.add2(hero3);
		singleLinkedList.add2(hero3);

		// 显示
		singleLinkedList.list();

		// 修改
		HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~~~~");
		System.out.println("修改后:");
		singleLinkedList.update(newHeroNode);
		singleLinkedList.list();

		// 删除
		singleLinkedList.dele(1);
		System.out.println("删除后:");
		singleLinkedList.list();

		// 获取有效节点的个数
		System.out.println("有效节点的个数=" + getLength(singleLinkedList.getHead()));

		// 测试倒数第k个节点
		HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 1);
		System.out.println(res);
		HeroNode res1 = findLastIndexNode(singleLinkedList.getHead(), 2);
		System.out.println(res1);

		// 测试单链表的反转
		System.out.println("测试链表:");
		singleLinkedList.list();
		System.out.println("反转之后:");
		reverseList(singleLinkedList.getHead());
		singleLinkedList.list();
		
		//逆序打印
		System.out.println("逆序打印:");
		reverseList(singleLinkedList.getHead());
		singleLinkedList.list();
	}

	// 逆序打印
	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后移,压入下一个节点
		}
		// 遍历栈中节点
		while (stack.size() > 0) {
			System.out.println(stack.pop());// 先入后出
		}

	}

	// 将单链表进行反转
	public static void reverseList(HeroNode head) {
		// 判断
		if (head.next == null || head.next.next == null) {
			return;
		}
		// 辅助变量(帮助遍历原来的链表)
		HeroNode cur = head.next;
		HeroNode next = null;// 指向当前节点[cur]的下一个节点
		HeroNode reverseHead = new HeroNode(0, "", "");// 新节点
		// 遍历原来的链表
		while (cur != null) {
			next = cur.next;// 暂时保存当前节点的下一个节点
			cur.next = reverseHead.next;// 将cur的下一个节点指向新的链表的头部节点
			reverseHead.next = cur;// 将cur链接到新的链表上
			cur = next;// 后移
		}
		// 将head.next指向reversHead.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) {
		// 判空:链表为空,返回null
		if (head.next == null) {
			return null;
		}
		// 第一次遍历:获取链表长度
		int size = getLength(head);
		// 第二次遍历:(size-index)就是我们倒数第index个节点

		// 数据校验
		if (index <= 0 || index > size) {
			return null;
		}
		// 辅助变量
		HeroNode cur = head.next;

		// for循环定位
		for (int i = 0; i < size - index; i++) {
			cur = cur.next;
		}
		return cur;

	}

	// 方法:获取有效节点 的个数(如果是带头结点的链表,需要不统计头结点)
	// head是头结点,length是有效节点个数
	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 SingleLinkedList {
	// 初始化头结点
	private HeroNode head = new HeroNode(0, "", "");

	// 返回头结点
	public HeroNode getHead() {
		return head;
	}

	public void setHead(HeroNode head) {
		this.head = head;
	}

	// 第一种添加节点的方式
	// 思路:在没有考虑排名编号的时候。
	// 1、找到当前链表的最后节点
	// 2、将最后这个节点的next指向新的节点
	public void add(HeroNode heroNode) {
		// 辅助指针
		HeroNode temp = head;
		// 循环遍历
		while (true) {
			// 寻找链表的最后
			if (temp.next == null) {
				break;
			}
			// 未找到,将temp后移
			temp = temp.next;
		}
		temp.next = heroNode;
	}

	// 第二种添加英雄的方式,根据排名插入指定位置(如果有这个排名,则添加失败,并且给出提示)
	public void add2(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;
				break;
			}
			temp = temp.next; // 后移,遍历
		}
		// 判断falg的值
		if (flag) {
			System.out.printf("编号%d存再,不能加入\n", heroNode.no);
		} else {
			// 插入链表中,temp后
			heroNode.next = temp.next;
			temp.next = heroNode;
		}

	}

	// 删除节点
	// 1.head不能动,因此需要temp辅助节点找到待删除节点的前一个节点。
	// 2.在比较的时候,是需要temp.next.no与待删除节点.no进行比较
	public void dele(int no) {
		HeroNode temp = head;
		boolean flag = false;// 标识是否找到待删除节点的前一个节点
		while (true) {
			if (temp.next == null) {// 已经到链表最后,退出
				break;
			}

			if (temp.next.no == no) {// 找到待删除节点的前一个节点temp
				flag = true;
				break;
			}
			temp = temp.next;// temp后移

		}
		// 判断flag
		if (flag) {// 找到
			temp.next = temp.next.next;

		} else {
			System.out.printf("要找的节点%d, 不存在\n", no);
		}
	}

	// 修改节点的信息
	public void update(HeroNode newHeroNode) {
		// 判空
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		// 找到需要的节点(辅助变量)
		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);
		}
	}

	// 显示链表
	public void list() {
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		HeroNode temp = head.next;
		while (true) {
			// 判断
			if (temp == null) {
				break;
			}
			// 不为空,输出节点信息
			System.out.println(temp);
			// 将next后移
			temp = temp.next;
		}
	}
}

//定义节点
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 + "]";
	}

}

输出

编号3存再,不能加入
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
修改后:
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=小卢, nickname=玉麒麟~~~~~]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
删除后:
HeroNode [no=2, name=小卢, nickname=玉麒麟~~~~~]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
有效节点的个数=3
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=3, name=吴用, nickname=智多星]
测试链表:
HeroNode [no=2, name=小卢, nickname=玉麒麟~~~~~]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
反转之后:
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=2, name=小卢, nickname=玉麒麟~~~~~]
测试逆序打印
HeroNode [no=2, name=小卢, nickname=玉麒麟~~~~~]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]