数据结构与算法day06-单链表面试题讲解(新浪、百度、腾讯)

单链表的常见面试题如下:

1.求单链表中有效节点的个数
2.查找单链表中的倒数第K个节点【新浪面试题】
3.单链表的反转【腾讯面试题】
4.从尾到头打印单链表【百度,要求方式1:反向遍历。方式2:stack栈】
5.合并两个有序的单链表,合并之后的链表依然有序【课后练习】

题1:代码如下:
// 获取单链表的有效节点个数(如果是带头结点的链表,需求不统计头结点)
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代码如下:
public static HeroNode findLastIndexNode(HeroNode head, int index) {
	// 判断如果链表为空,返回null
	if (head.next == null) {
		return null;
	}
	// 第一个遍历得到链表的长度(节点个数)
	int size = getLength(head);
	// 第二次遍历size-index位置,就是我们倒数的第K个节点
	// 先做一个index校验
	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;
}

题3链表翻转示意图如下数据结构与算法day06-单链表面试题讲解(新浪、百度、腾讯)

	// 链表翻转思路(较难)
	// 1.先定义一个节点reverseHead = new HeroNode();
	// 2.从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在心的链表reverseHead的最前端
	// 原来的链表的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, "", "");
		// 遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表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;
	}


	// 题4逆序打印思路:
	// 方式1:先将单链表翻转,再遍历即可,这样做会破坏原来的单链表结构
	// 方式2:利用栈这个数据结构,将各个 节点压入到栈中,利用栈的先进后出,实现效果
	// 综上,使用方式2,实现逆序打印单链表

栈的演示:

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

逆序打印的代码实现:

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.add也可以
		stack.push(cur);
		cur = cur.next; // cur后移,就可以压入下一个
	}
	// 将栈的节点进行打印,pop
	while (stack.size() > 0) {
		System.out.println(stack.pop()); // stack的特点是先进后出
	}
}
上一篇:002_4、Python None(空值)及用法


下一篇:Day06