目录
学习了单链表的应用（面试题）
1. 求单链表的有效节点
- 思路：
-
1、新增辅助变量num，用于记录单链表有效节点的个数，新增curNode指针，用于遍历单链表的所有节点
-
2、num在遍历单链表的所有节点过程中，自增
-
3、得出的num即为单链表的有效节点
- 代码：
-
//获的链表的长度
-
public static int getLength(HeroNode headNode) {
-
if(headNode ==
null||headNode.next ==
null) {
-
return
0;
-
}
-
HeroNode curHeroNode = headNode.next;
-
int num =
0;
-
while(curHeroNode!=
null) {
-
num++;
-
curHeroNode = curHeroNode.next;
-
}
-
return num;
-
}
2. 查找单链表倒数第K个节点（新浪面试题）
- 思路
-
1、遍历单链表，算出来单链表的长度，记为
length
-
2、从头再次遍历单单链表，遍历到第（
length - K）个节点时停止，即为倒数第K个节点。
- 代码：
-
//获的倒数第K个节点
-
private static HeroNode getLastIndexNode(HeroNode headNode, int k) {
-
if(headNode ==
null ||headNode.next ==
null) {
-
return
null;
-
}
-
int size = getLength(headNode);
-
//校验k是否合理
-
if(k <
0||k > size) {
-
return
null;
-
}
-
HeroNode curHeroNode = headNode.next;
-
for (
int i =
0; i <(size-k) ; i++) {
//3-1=2
-
curHeroNode = curHeroNode.next;
-
}
-
// TODO Auto-generated method stub
-
return curHeroNode;
-
}
- 备注：
1、别忘了校验下K的合理性3. 单链表的翻转（腾讯面试题）
- 思路：
-
1、新添加个头节点，用于盛放翻转后的单链表
-
reverseHeadNode =
new HeroNode();
-
2、新创建curNode和nextNode指针，用于指向原链表的节点，用curNode指针遍历单链表，每次遍历的节点，全部插入到reverseHeadNode头节点的后面
-
3、遍历完成后，将headNode头节点指向reverseHeadNode.
next.
- 代码：
-
//翻转单链表
-
private static void reverseLinkList(HeroNode headNode) {
-
//如果链表为空或者只包含一个节点，返回空；
-
if(headNode.next ==
null || headNode.next.next ==
null ) {
-
return;
-
}
-
//定义辅助指针，用来遍历单链表
-
HeroNode curNode = headNode.next;
-
HeroNode nextNode =
null;
-
//定义个新头节点，用于盛放翻转后的单链表
-
HeroNode reverseHeadNode =
new HeroNode(
0,
"",
"");
-
while(curNode !=
null) {
-
nextNode = curNode.next;
-
curNode.next = reverseHeadNode.next;
-
reverseHeadNode.next = curNode;
-
curNode = nextNode;
-
}
-
headNode.next = reverseHeadNode.next;
-
}
- 备注：
1、nextNode指针是必须有的，因为他记录着遍历时下个节点的位置信息（将curNode节点插入到reverseHeadNode节点后，这个节点已经被摘除了，此时只能靠着nextNode节点来继续遍历下个节点）4. 从尾到头打印单链表（百度面试题）
- 思路：
-
1、可以先翻转，再打印，但是这样就破坏了原链表的结构（不提倡）
-
2、可以应用栈，遍历单链表时，将每个单链表压栈，遍历完成后，再出栈，此时出栈的顺序就是从未到头打印单链表的顺序
- 代码：
-
//单链表翻转打印
-
private static void reversePrint(HeroNode headNode) {
-
if(headNode.next == null) {
-
return;
-
}
-
Stack<HeroNode>
stack =
new Stack<HeroNode>();
-
HeroNode curNode = headNode.next;
-
while(curNode != null) {
-
stack.push(curNode);
-
curNode = curNode.next;
-
}
-
while(
stack.size()>
0) {
-
System.out.println(
stack.pop());
-
}
-
}
- 备注：
应用栈的先入后出的原理，倒序打印单链表节点信息5. 合并两个有序单链表，合并之后，依然有序
- 思路：
-
1、思路一：新建个单链表C，比较前两个单链表的每个节点，节点小的放C尾部
-
2、思路二：已其中一个单链表为基准A，让另一个单链表插入A中
- 代码：
思路一的代码：
-
private static SingleLinkList togetherToVerse(HeroNode headNode1, HeroNode headNode2) {
-
SingleLinkList singleLinkList = new SingleLinkList();
-
HeroNode headNode3 = singleLinkList.getHeadNode();
-
// 看两个单链表是否是空
-
if (headNode1.next ==
null) {
-
headNode3.next = headNode2.next;
-
return singleLinkList;
-
}
-
if (headNode2.next ==
null) {
-
headNode3.next = headNode1.next;
-
return singleLinkList;
-
}
-
-
-
//都不为空的话，同时遍历两个链表，每次比较两个链表的节点，取出最小的元素，排在singleLinkList后面
-
HeroNode curNode1 = headNode1.next;
-
HeroNode nextNode1 =
null;
-
HeroNode curNode2 = headNode2.next;
-
HeroNode nextNode2 =
null;
-
HeroNode curNode3 = headNode3;
-
-
while (
true) {
-
if (curNode1 ==
null || curNode2 ==
null) {
-
break;
-
}
-
if (curNode1.getNo() <= curNode2.getNo()) {
-
System.
out.println(
"添加了curNode1的数据：" + curNode1.getNo());
-
-
nextNode1 = curNode1.next;
-
curNode1.next =
null;
-
curNode3.next = curNode1;
-
curNode1 = nextNode1;
-
// System.out.println("添加了curNode1的数据后下一个数据是："+curNode1.getNo());
-
curNode3 = curNode3.next;
-
}
else {
-
System.
out.println(
"添加了curNode2的数据：" + curNode2.getNo());
-
// curNode2 = curNode2.next;
-
nextNode2 = curNode2.next;
-
curNode2.next =
null;
-
curNode3.next = curNode2;
-
curNode2 = nextNode2;
-
// System.out.println("添加了curNode2的数据后的数据："+curNode2.getNo());
-
curNode3 = curNode3.next;
-
}
-
}
-
if (curNode1 ==
null && curNode2 !=
null) {
-
System.
out.println(
"1");
-
curNode3.next = curNode2;
-
}
-
if (curNode1 !=
null && curNode2 ==
null) {
-
System.
out.println(
"2");
-
System.
out.println(curNode1.getNo());
-
-
curNode3.next = curNode1;
-
}
-
return singleLinkList;
-
}
思路二代码：
-
private static void togetherToVerse1(HeroNode headNode1,HeroNode headNode2) {
-
if(headNode1.next ==
null) {
-
headNode1.next = headNode2.next;
-
return;
-
}
-
if(headNode2.next ==
null) {
-
return;
-
}
-
HeroNode curNode1 = headNode1.next;
-
HeroNode preNode1 = headNode1;
-
-
HeroNode curNode2 = headNode2.next;
-
HeroNode nextNode2 =
null;
-
-
while(
true) {
-
if(curNode1 ==
null || curNode2 ==
null) {
-
break;
-
}
-
if(curNode1.getNo() < curNode2.getNo()) {
-
System.
out.println(
"curNode1.getNo() < curNode2.getNo()------curNode1:"+curNode1.getNo()+
" "+
"curNode2:"+curNode2.getNo());
-
preNode1 = curNode1;
-
curNode1 = curNode1.next;
-
}
else {
-
System.
out.println(
"curNode1.getNo() >= curNode2.getNo()------curNode1:"+curNode1.getNo()+
" "+
"curNode2:"+curNode2.getNo());
-
//插入
-
nextNode2 = curNode2.next;
-
curNode2.next = curNode1;
-
preNode1.next = curNode2;
-
preNode1 = curNode2;
-
curNode2 = nextNode2;
-
}
-
}
-
if(curNode1 ==
null && curNode2 !=
null) {
-
preNode1.next = curNode2;
-
}
-
-
-
-
}
- 备注：
-
1、这个代码弄得我蛋疼，切记，同一个节点，千万不能既让单链表一添加，又让链表二添加，否则，链表二的会覆盖链表一的；
-
2、当遇到遍历插入的运算是，一定要想到nextNode指针，且不能直接写node = node.
next;
转载：https://blog.csdn.net/wangjiaee/article/details/105682958
查看评论