前言
- 总结一下单链表的面试题，对其详细的描述。
- 这个的方法 我都放在了 SingleLinkedListMain 类中，写成了静态方法。
一、 求单链表中有效的个数
1.1 问题描述
求单链表中有效节点的个数
1.2 思路分析
直接遍历即可，设置一个增加器。
1.3 代码实现
/*
* 方法：获取单链表的有效节点个数（如果是带头结点的链表，需要不统计头结点）
* @param head 链表的头节点
* @return 返回的就是有效节点的个数
* */
public static int getLength(HeroNode head) {
if (head.next == null) {
return 0;
}
HeroNode temp = head.next;
int count = 0;
/*while (true){
if (temp== null){
break;
}
count++;
temp = temp.next;
}*/
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
二、 新浪面试题
2.1 问题描述
查找单链表中的倒数第k个结点
2.2 思路分析
思路：
- 编写一个方法，接收head节点，同时接收一个index
- index 表示是倒数第index个节点
先把链表从头到尾遍历，得到链表的总的长度 size = getLength(), 这个方法 为上面例题。- 对index 进行数据校验，小于0，大于size，都返回null。
- 得到size 后，我们
从链表的第一个开始遍历 (size-index)个，就得到了 倒数第K个节点。 - 如果找到了，则返回该节点，否则返回nulll
2.3 代码实现
/*
* 方法：查找单链表中的倒数第k个结点 【新浪面试题】
* 思路：
* 1. 编写一个方法，接收head节点，同时接收一个index
* 2. index 表示是倒数第index个节点
* 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
* 4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
* 5. 如果找到了，则返回该节点，否则返回nulll
* */
public static HeroNode findLastIndexNode(HeroNode head, int index) {
//判断如果链表为空，返回null
if (head.next == null) {
return null;
}
//第一次遍历得到链表的长度(节点个数)
int size = getLength(head);
//先做一个index的校验
if (index < 0 || index > size) {
return null;
}
//第二次遍历 size-index 位置，就是我们倒数的第K个节点
//定义给辅助变量， for 循环定位到倒数的index
HeroNode temp = head.next;
for (int i = 0; i < size - index; i++) {
temp = temp.next;
}
return temp;
}
三、 腾讯面试题【有难度】
3.1 问题描述
将单链表反转。
3.2 思路分析
思路：
- 先定义一个节点
HeroNode reverseHead = new HeroNode(0, "", ""); - 在定义一个 辅助节点和 next节点（用于存放当前节点的下一个节点，因为后面需要使用）。
HeroNode temp = head.next;HeroNode next = null; 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端。temp.next = reverseHead.next，这句话就是将反转链表的后面赋给拿下来的 temp 当前节点。- 将当前拿下来的节点，放到 reverseHead 上。
- 最后，将 temp 节点后移：
temp = next;
3.3 代码实现
/*
* 将单链表反转 【腾讯面试题】
* */
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, "", "");
/*
* 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
* 动脑筋
* */
while (temp != null) {
next = temp.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
temp.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
reverseHead.next = temp;//将cur 连接到新的链表上
temp = next;//让cur后移
}
//将head.next 指向 reverseHead.next , 实现单链表的反转
head.next = reverseHead.next;
}
四、 百度面试题
4.1 问题描述
从尾到头打印单链表
4.2 思路分析
- 第一种方式： 反向遍历。先将链表反转，在遍历打印（借用腾讯面试题）。但是这样会改变链表数据结构，而题目仅是逆序打印而已。
- 第二种方式：借用stack 栈 的先进后出的特点来完成逆序打印。
- 思路分析：
可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.
举例演示栈的使用 Stack
4.3 代码实现
/*
* 方法：实现单链表的逆序打印【百度面试题】
* 方式1：先反转，在打印。
* 方式2：利用栈 这个数据结构，将各个节点压入栈中，然后利用栈的先进先出的特点，实现逆序打印的效果
* */
public static void reversePrint(HeroNode head){
if (head.next == null){
return;
}
Stack<HeroNode> stack = new Stack<>();
HeroNode temp = head.next;
while (temp != null){
stack.push(temp);
temp = temp.next;
}
while (stack.size()>0){
System.out.println(stack.pop());
}
}
五、所有测试放一块
package com.feng.ch03_singlelinkedlist;
import java.util.Stack;
public class SingleLinkedListMain {
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.addLinked(hero1);
// singleLinkedList.addLinked(hero2);
// singleLinkedList.addLinked(hero4);
// singleLinkedList.addLinked(hero3);
singleLinkedList.addLinkedByOrder(hero1);
singleLinkedList.addLinkedByOrder(hero2);
singleLinkedList.addLinkedByOrder(hero4);
singleLinkedList.addLinkedByOrder(hero3);
// 显示节点
System.out.println("显示初始添加后的节点~");
singleLinkedList.list();
// 测试修改
System.out.println();
System.out.println("测试修改后的结果");
HeroNode updateNode = new HeroNode(2, "小卢", "玉麒麟");
singleLinkedList.updateNode(updateNode);
singleLinkedList.list();
// 测试删除
System.out.println();
System.out.println("测试删除后的结果");
singleLinkedList.deleteNode(2);
singleLinkedList.deleteNode(3);
singleLinkedList.list();
// 测试返回单链表有效个数
System.out.println();
System.out.println("单链表有效个数=" + getLength(singleLinkedList.getHead()));
// 测试 查看倒数第 K 个节点的 数据
System.out.println();
HeroNode lastIndexNode = findLastIndexNode(singleLinkedList.getHead(), 1);
System.out.println("倒数第 K 个节点的res=" + lastIndexNode);
// 测试单链表的反转
System.out.println();
System.out.println("测试反转后的链表");
reverseList(singleLinkedList.getHead());
singleLinkedList.list();
// 测试单链表的逆序打印
System.out.println();
System.out.println("测试单链表的逆序打印");
reversePrint(singleLinkedList.getHead());
}
}
