1.计算单链表中有效节点个数

1）思路：

定义一个变量，定义一个临时节点，遍历单链表，临时节点后移，变量就自增

public class linkedList {public static void main(String[] args) {//创建heroNode的对象HeroNode h1 = new HeroNode(1,"宋江","及时雨");HeroNode h2 = new HeroNode(2,"卢俊义","玉麒麟");HeroNode h3 = new HeroNode(3,"吴用","智多星");HeroNode h4 = new HeroNode(4,"林冲","豹子头");HeroNode h5 = new HeroNode(4,"刻晴","玉衡星");//创建单链表对象SingerLinkedList singerLinkedList = new SingerLinkedList();singerLinkedList.addByOrder(h1);singerLinkedList.addByOrder(h4);singerLinkedList.addByOrder(h3);singerLinkedList.addByOrder(h2);singerLinkedList.show();int number = list.nodeNumber(singerLinkedList.getHead());System.out.println("有效节点的个数是：" + number);}//计算单链表中有效节点个数//思路：//1.定义一个变量，定义一个临时节点，遍历单链表，临时节点后移，变量就自增public int nodeNumber(HeroNode head){if(head.next == null){return 0;}int length = 0;//定义一个变量。用来保存有效节点个数HeroNode temp = head.next; //定义一个临时节点while(true){if(temp == null){break;}length++;//变量自增temp = temp.next; //临时节点后移}return length;}
}//创建单链表：每一个英雄代表一个节点
class SingerLinkedList{private HeroNode head; //头节点：不存放具体的数据，用于定位单链表public HeroNode getHead() {return head;}public void setHead(HeroNode head) {this.head = head;}public SingerLinkedList() {head = new HeroNode(0,"","");}//添加节点到单链表public void addByOrder(HeroNode node){//定义一个辅助变量temp代替headHeroNode temp = head;boolean flag = false; //用于处理重复节点while(true){if(temp.next == null){//找到当前单链表的最后一个节点break;}if(node.no < temp.next.no){ //要插入的节点的排名 要小于 要插入的节点的下一个节点的排名break;}if(node.no == temp.next.no){//有重复的节点，使其无法插入flag = true;break;}temp = temp.next;}if(flag){System.out.println("插入数据重复，" + "重复编号为：" + node.no); //重复的节点无法插入}else{node.next = temp.next; //要插入的节点的next = temp.nexttemp.next = node; //temp.next = 要插入的节点}}//遍历单链表public void show(){//判断单链表是否为空if(head.next == null){System.out.println("单链表为空~~");return;}//定义一个辅助变量tempHeroNode temp = head.next;//因为单链表至少有一个值while(true){if(temp == null){//找到当前单链表的最后一个节点的下一节点break;}System.out.println(temp);temp = temp.next; //temp后移}}
}
//创建英雄节点
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;}@Overridepublic String toString() {return "heroNode{" +"no=" + no +", name='" + name + '\'' +", nickName='" + nickName + '\'' +'}';}
}

2.查找单链表中倒数第k个节点

1）思路：

1.编写一个方法，接收head，同时接收一个index
2.遍历单链表，获取单链表长度
3.得到单链表长度size，就可以再遍历（size - index）个节点，让辅助节点后移，直到移到倒数第index个位置
4.如果找到了，返回该节点。未找到，返回null

//查找单链表中倒数第k个节点
public HeroNode findLastIndexNode(HeroNode head,int index){if(head.next == null){return null;//空链表，不能打印}HeroNode temp = head.next;int size = nodeNumber(head);for (int i = 0; i < (size - index); i++) {temp = temp.next;}return temp;}

3.单向链表的反转

1）定义一个新的头节点，遍历单链表，依次往新的链表中插入数据，最后将数据连接会原来的头节点。
2）步骤：
①

②

③

④

⑤

3）代码：

public void reverseList(HeroNode head){if(head.next == null){return;//空链表，不能打印}HeroNode reverseHead = new HeroNode(0,"","");//定义一个新的头节点HeroNode temp = head.next;HeroNode next;while(temp != null){next = temp.next;temp.next = reverseHead.next;reverseHead.next = temp;temp = next;}head.next = reverseHead.next;}

4.从尾到头打印单链表（要求1：反向遍历，要求2：Stack栈）

1）反向遍历如上所示
2）Stack栈：

栈是先进后出

//Stack栈处理：从尾到头打印单链表public void reversePrint(HeroNode head){if(head.next == null){return;}HeroNode temp = head.next; //方便遍历链表//创建一个栈，将各个节点压入栈中Stack<HeroNode> stack = new Stack();while(temp != null){stack.push(temp);temp = temp.next;//temp后移，方便压入下一个节点}//将栈中的节点进行打印，pop出栈while(stack.size() > 0){System.out.println(stack.pop());}}