1.求单链表中有效节点的个数
//方法:获取到单链表的节点的个数(如果是带头节点的链表,不统计头节点)
/**
*
* @param head 链表的头节点
* @return 返回有效节点的个数
*/
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.查找单链表中的倒数第k个节点【新浪】
//查找单链表中的倒数第k个节点【新浪】
/*
思路
1.编写一个方法,接受head节点,同时接收一个index
2.index表示的是倒数第index个节点
3.先把链表从头到尾遍历,得到链表的总长度getLength
4.得到size后,从链表的第一个开始遍历(size-index)个,就可以得到
5.如果找到了就返回该节点,否则返回空
*/
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;
}
//定义一个辅助变量
HeroNode cur = head.next;
for (int i = 0; i < size-index; i++) {
cur = cur.next;
}
return cur;
}
3.单链表的反转【腾讯】
思路
1.先定义一个头节点 reverseHead = new HeroHead();
2.从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表 reverseHead 的最前端
3.原来的链表的 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;
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
//演示栈Stack的基本使用
public class TestStack {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
//入栈
stack.add("apple");
stack.add("banana");
stack.add("orange");
//出栈
while (stack.size() > 0) {
System.out.println(stack.pop()); //pop就是将栈顶的元素取出
}
}
}
/*
使用方式2
利用栈这个数据结构,将各个节点压入到栈中,
然后利用栈的先进后出的特点,实现逆序打印的效果
*/
public static void reversePrint(HeroNode head) {
if (head.next == null) {
return; //空链表,不能打印
}
//创建一个栈,将各节点压入栈
Stack<HeroNode> stack = new Stack<>();
HeroNode cur = head.next;
//将链表的所有节点压入栈
while (cur != null) {
stack.push(cur);
cur = cur.next; //cur后移,这样就可以压入下一个节点
}
//将栈中的节点进行打印,pop出栈
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}