- 第一题，求单链表中有效节点的个数
- 第二题，查找单链表中倒数第K个结点
- 第三题，单链表的反转
- 第四题，从尾到头打印单链表
package com.spx.list;
import java.util.Stack;
public class SinglelinkedListDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 测试一下
// 先创建几个节点
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.add(hero1);
// singlelinkedList.add(hero2);
// singlelinkedList.add(hero3);
// singlelinkedList.add(hero4);
// 测试一下，求单链表中有效结点个个数
System.out.println("有效的节点个数为"+getLength(singlelinkedList.getHead()));//2
// 测试一下，看看是否得到了倒数第k个节点
HeroNode res=findLastIndexNode(singlelinkedList.getHead(), 1);
System.out.println("res="+res);
// 测试一下单链表的反转功能
System.out.println("原来链表的情况");
singlelinkedList.list();
System.out.println("反转单链表");
reversetList(singlelinkedList.getHead());
singlelinkedList.list();
// 测试一下单链表的逆序打印
System.out.println("测试逆序打印单链表,没有改变链表的本身结构");
reversePrint(singlelinkedList.getHead());
}
// 从尾到头打印单链表
// 使用方式二
public static void reversePrint(HeroNode head) {
if(head.next == null) {
return;//空链表，不能打印
}
// 创建一个栈，将各个节点压入栈中
Stack 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());//stack的特点是先进后出
}
}
// 单链表的反转
public static void reversetList(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;
}
// 查找单链表中倒数第K个结点
// 思路
// 1、编写一个方法，接收head节点，同时接收一个index
// 2、index表示是倒数第index个节点
// 3、先把链表从头到尾遍历，获得链表的总长度，调用getlength方法
// 4、得到size后，从链表的第一个开始遍历(size-index)个，就可以得到
// 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;//3
for(int i=0 ; i < size-index ; i++) {
cur=cur.next;
}
return cur;
}
//获取单链表的节点的个数
//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;
}
}
//定义一个heronode，每个heronode对象就是一个节点
class HeroNode{
public int no;
public String name;
public String nickName;
public HeroNode next;//指向下一个节点
// 构造器
public HeroNode(int no,String name,String nickName) {
this.no=no;
this.name=name;
this.nickName=nickName;
}
// 为了显示方便，重写tostring方法
@Override
public String toString() {
return "Heronode [no=" + no + ", name=" + name + ", nickName=" + nickName+"]";
}
}
