前言
本篇将讲述之前新浪、百度、腾讯的单链表的面试题
单链表面试题
（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;
}
需在SingleLinkedList.class类中添加返回头节点方法：
//返回头节点
public HeroNode getHead(){
return head;
}
（2）查找单链表中的倒数第k个节点【新浪面试题】
思路： > > 1. 1.编写一个方法，接收head节点，同时接收一个index > > 2. 2.index表示是倒数第index个节点 > 3. 3.先把链表从头到尾遍历，得到链表的总的长度getLength > 4. 4.得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到 > 5. 5.如果找到了，则返回该节点，否则返回Null
代码
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）单链表的反转【腾讯面试题，有点难度】
图解
思路： > > 1. 1.先定义一个节点
reverseHead = new HeroNode();> 2. 2.从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端。 > 3. 3.原来的链表的head.next=reverseHead.next
代码实现
//将单链表反转
public static void reversetList(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：Stack栈
图像分析
思路 > > 1. 1.上面的题的要求就是逆序打印单链表 > 2. 2.方式1：先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议； > 3. 3.方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果。
代码实现
测试Stack的使用
//演示Stack的基本使用
public class TestStack {
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());//pop就是将栈顶的数据取出
}
}
}
输出结果
smith
tom
jack
代码
//方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.
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后移，这样可以压入下一个节点
}
//将栈中的节点进行打印，pop出栈
while(stack.size()>0){
System.out.println(stack.pop());//stack的特点是先进先出
}
}
（5）合并两个有序的单链表，合并之后的链表依然有序
未完成
