Day04单链表面试题

单链表常见面试题（新浪、百度、腾讯）

1、求单链表中有效节点的个数(很简单)

实现代码

/*** 常见面试题1：获取单链表的有效元素个数* 思路:直接遍历（但是要排除头结点）*/
public static int getValidNode(HeroNode head){int num = 0;// 链表为空if (head.next == null){return num;}// 排除头结点HeroNode temp = head.next;while (temp != null){// 有效节点数+1num++;// 后移temp = temp.next;}return num;
}

测试代码

public static void main(String[] args) {HeroNode node1 = new HeroNode(1, "李逵", "黑旋风");HeroNode node2 = new HeroNode(2, "宋江", "及时雨");HeroNode node3 = new HeroNode(3, "吴用", "智多星");HeroNode node4 = new HeroNode(4, "林冲", "豹子头");// 初始化链表SingleLinkedList linkedList = new SingleLinkedList();// 添加英雄linkedList.addByOrder(node1);linkedList.addByOrder(node4);linkedList.addByOrder(node4);linkedList.addByOrder(node3);linkedList.addByOrder(node3);linkedList.addByOrder(node2);// 打印linkedList.findAllLink();// 统计节点有效个数System.out.println("有效的英雄节点数为：" + getValidNode(linkedList.getHead()));
}

结果

2、查找单链表中的倒数第k个结点 【新浪面试题】

实现代码

/*** 常见面试题2：查找单链表中的 倒数 第k个结点 【新浪面试题】* 思路：* 1、首先获取有效的节点数，并将 倒数 第几位转换成 正数 第几位* 2、利用循环遍历，设置一个哨兵来计数，然后和正数的进行比对，相等即为找到目标！*/
public static HeroNode findInverseNode(HeroNode head, int n) {if (head.next == null) {return null;}// 排除头结点HeroNode cur = head.next;int validNum = getValidNode(head);boolean flag = false;// 对于 请求参数的合法性校验if (n > validNum || n < 0) {return null;}// 转换成 正数 的n = validNum - n;// 计数用的哨兵int count = 0;// 当然这里也可以用for循环while (true) {if (cur == null) {break;}if (n == count) {// 找到目标flag = true;break;}count++;// 后移cur = cur.next;}if (flag) {return cur;}return null;
}

测试代码

// 查找单链表中的 倒数 第k个结点
int k = 4;
System.out.println("英雄信息为：" + findInverseNode(linkedList.getHead(), k));

效果图

3、单链表的反转【腾讯面试题，有点难度】

实现代码

/*** 常见面试题3：单链表的反转【腾讯面试题，有点难度】* 思路：* 1、首先定义一个新的节点（cur）* 2、然后遍历原来的head节点，没遍历一个节点，就将其添加到cur中，只不过要用头插法！！！*/
public static HeroNode reverseLink(HeroNode head) {// 当只有一个节点，或者一个节点都没有时if (head.next == null || head.next.next == null) {System.out.println("无需反转");return head;}// 遍历正向链表的（原来的链表）HeroNode temp = head.next;// 存储临时的temp变量（注意事项是地址传递）HeroNode copy = null;// 存储反向链表的HeroNode reverseHead = new HeroNode(0, "", "");while (temp != null) {// 赋值 （注意这里是地址传递，并非值传递）copy = temp;// 后移temp = temp.next;// 头插法copy.next = reverseHead.next;reverseHead.next = copy;}return reverseHead;
}/*** 查询全部节点* @param head*/
public static void queryAll(HeroNode head) {HeroNode temp = head.next;int i = 1;if (head.next == null) {System.out.println("当前链表为空，无数据可以打印！");return;}while (temp != null) {System.out.println("第" + i + "个英雄信息如下:" + temp.toString());// 后移temp = temp.next;i++;}
}

测试代码

// 反向链表
System.out.println("反向链表");
HeroNode reverseLink = reverseLink(linkedList.getHead());
queryAll(reverseLink);

效果图

4、从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】

方式1：反向遍历：其实就是反转链表（就是第三道面试题的方法），不建议使用，因为那样会破坏原有的链表结构！万一后续需要在打印正向链表呢，所以只改变打印顺序即可。

方式2：Stack栈

实现代码

/*** 常见面试题4：从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】*/
public static Stack<HeroNode> reservePrintLink(HeroNode head) {Stack<HeroNode> stack = new Stack<>();HeroNode temp = head.next;if (head.next == null) {System.out.println("当前链表为空，无数据可以打印！");return null;}while (temp != null) {// 入栈stack.push(temp);// 后移temp = temp.next;}return stack;
}/*** 循环遍历Stack*/
public static void getAllStack(Stack stack){while(stack.size() > 0){System.out.println(stack.pop() + "出栈");}
}

测试代码

// 方向打印链表
System.out.println("测试反向链表打印");
Stack<HeroNode> nodeStack = reservePrintLink(linkedList.getHead());
getAllStack(nodeStack);

运行结果

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！