话不多说，直接看代码实现：
代码实现： package com.sai.ssss.linkedList; import java.util.Stack; /** * @Author sai * @Description 单链表的面试题 * @Time 2020-07-02 15:24 */ class SingleLinkedList_Demo { static class SingleLinkedList{ //创建头节点 public static HeadNode head = new HeadNode(0,"",""); /** * 添加链表 * @param headNode * 1.找到位置 * 2.设置位置前一个个节点的指针指向，和添加数据的指针方向 */ public void addByOrder(HeadNode headNode){ HeadNode temp = head; Boolean q = false; while (true){ if(temp.next == null){ //队列尾部 break; } if(temp.next.no > headNode.no){ //找到真确的位置 break; } else if(temp.next.no == headNode.no){ //已有该编号 q = true; break; } temp = temp.next; //以上三种都不是，指向下一个继续判断 } if(q){ System.out.println("该编号以存在~"); } else{ headNode.next = temp.next; //将要添加的数据的next域指向后一个 temp.next = headNode; //将要添加数据的前一个的next域指向要添加的数据 } } /** * 查询全部链表的方法 */ public void find(){ //判断链表是否为空 if(head.next == null){ System.out.println("此链表为空~"); return; } HeadNode temp = head.next; //头部节点往后的节点 while (true){ //判断节点是否最后 if(temp == null){ break; } System.out.println(temp.toString()); //输出节点信息 temp = temp.next; //将节点指针向后移 } } /** * 第一题：计算单链表的长度 * @param head * @return */ public int getLenght(HeadNode head){ HeadNode temp = head; if(temp.next == null){ System.out.println("此链表为空~"); } int sum = 0; Boolean falg = false; while (true){ if(temp.next == null){ //到达尾部 break; } sum++; temp = temp.next; } return sum; } /** * 第二题：查找倒数第K个元素 * @param headNode * @param k * 1.获取链表的总长度 * 2.第K位 = 总长度-k */ public HeadNode findK(HeadNode headNode,int k){ if(headNode.next == null){ //判断是否为空 return null; } int lenght = getLenght(headNode); //获取长度 if(k>lenght || k<=0){ //判断是否无效 return null; } HeadNode temp = headNode.next; for(int i=0;i<lenght-k;i++){ temp = temp.next; } return temp; } /** * 第三题：单链表的反转 * @return * 1.遍历链表，每遍历一个节点，就把该节点放到链表的最前端 */ public static void getReversal(HeadNode headNode){ if(headNode.next==null || headNode.next.next==null){ //判断链表是否为空，或者只有一个节点 return; } HeadNode temp = headNode.next; //辅助指针 HeadNode next = null; //保留当前节点的下一个节点 HeadNode reversal = new HeadNode(0,"",""); //创建反转后的头节点 while (temp != null){ next = temp.next; //保存当前节点的下一个节点 temp.next = reversal.next; //将temp的下一个节点指向新的链表的最前端 reversal.next = temp; //将temp连接到新的链表上 temp = next; //指针后移 } headNode.next = reversal.next; //原来的头部指向转换后的头部,实现链表反转 } public static HeadNode getHead() { return head; } } /** * 第四题：单链表的反向输出 * 利用栈的特性（先进后出），将链表存入到栈中，然后再拿出来 */ public void getReversalOutPut(HeadNode head){ if(head.next==null){ //判断链表是否为空 System.out.println("链表为空~"); return; } HeadNode temp = head.next; //辅助指针 Stack<HeadNode> s = new Stack<HeadNode>(); while (temp != null){ s.push(temp); temp = temp.next; } while (s.size() > 0){ System.out.println(s.pop()); } } /** * 设置一个实体类 */ static class HeadNode { private int no; //编号 private String name; //姓名 private String nackName; //诨名 private HeadNode next; //指针（next域） //构造方法 public HeadNode(int no, String name, String nackName) { this.no = no; this.name = name; this.nackName = nackName; } @Override public String toString() { return "HeadNode{" + "no=" + no + ", name='" + name + '\'' + ", nackName='" + nackName + '\''+ '}'; } } } 测试类： package com.sai.ssss.linkedList; /** * @Author sai * @Description SingleLinkedList_Demo的测试类 * @Time 2020-07-01 14:59 */ public class SingleLinkedList_Demo_Test { public static void main(String[] args) { SingleLinkedList_Demo.HeadNode headNode1 = new SingleLinkedList_Demo.HeadNode(1,"宋江","及时雨"); SingleLinkedList_Demo.HeadNode headNode2 = new SingleLinkedList_Demo.HeadNode(2,"卢俊义","玉麒麟"); SingleLinkedList_Demo.HeadNode headNode3 = new SingleLinkedList_Demo.HeadNode(3,"吴用","智多星"); SingleLinkedList_Demo.HeadNode headNode4 = new SingleLinkedList_Demo.HeadNode(4,"公孙胜","入云龙"); SingleLinkedList_Demo.SingleLinkedList singleLinkedList = new SingleLinkedList_Demo.SingleLinkedList(); //根据编号添加 singleLinkedList.addByOrder(headNode1); singleLinkedList.addByOrder(headNode4); singleLinkedList.addByOrder(headNode2); singleLinkedList.addByOrder(headNode3); //遍历输出 singleLinkedList.find(); System.out.println(); //1.获取链表的长度 //int i = singleLinkedList.getLenght(SingleLinkedList_Demo.SingleLinkedList.getHead()); //System.out.println("该单链表的长度为："+i); //2.输出倒数第K个节点 //System.out.println(singleLinkedList.findK(SingleLinkedList_Demo.SingleLinkedList.getHead(),1)); //3.反转链表 //singleLinkedList.getReversal(SingleLinkedList_Demo.SingleLinkedList.getHead()); //singleLinkedList.find(); //4.利用栈的特性，反向输出 singleLinkedList.getReversalOutPut(SingleLinkedList_Demo.SingleLinkedList.getHead()); } }