数据结构05——单链表面试题(有效节点的个数、查找单链表中的倒数第k个节点、单链表反转、逆序打印单链表（栈实现）)

1. 求单链表有效节点的个数

// 1. 求单链表有效节点的个数 public int accountLink() { // 获取指针 HeroLink temp = head; // 统计有效节点的个数 int count = 0; while (true) { if (temp.next == null) // 遍历到最后一个节点 break; else { count++; temp = temp.next; } } return count; }

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

// 2. 查找单链表中的倒数第k个节点 public HeroLink findAverK(int k) { if (head.next == null) { return null; } // 首先判断，是否有那么多元素 int sumLink = accountLink() + 1; //有效节点加头节点 if (k > sumLink) { System.out.println("没有那么多元素：" + k); return null; } int s = (sumLink - k); HeroLink temp = head; while (s > 0) { s--; temp = temp.next; } return temp; }

3. 单链表反转

前插，思路分析

代码实现

后插，代码实现

// 3. 单链表反转，后插 public SingleList averLinkList(SingleList singleList) { // 1. 创建一个新的头节点 HeroLink newHeroLinkHead = new HeroLink(0, "", ""); // 2. 遍历原来的链表，每次取第一个元素，插入到新的头节点的第一个元素的位置 // 判断链表是否为空 if (singleList.getHead().next == null) { System.out.println("链表为空！！！"); return null; } // 传来的单链表的指针 HeroLink temp = singleList.getHead(); // 新的单链表的指针 HeroLink newTemp = newHeroLinkHead; // 开始遍历 while (temp.next != null) { while (true) { if (temp.next.next == null) { // 遍历到最后一个节点的头一个节点，取出最后一个节点 newTemp.next = temp.next; temp.next = null; newTemp = newTemp.next; break; } temp = temp.next; } // 重置指针，开始下一次遍历 temp = singleList.getHead(); } // 传来链表的头节点指向，新链表的头节点 singleList.getHead().next = newHeroLinkHead.next; return singleList; }

4. 逆序打印单链表

思路分析

代码实现

// 4. 逆序打印单链表 public void reverseShow(SingleList singleList) { // 判断链表是否为空 if (singleList.getHead().next == null) { System.out.println("链表为空！！！"); return; } // 传来的单链表的指针 HeroLink temp = singleList.getHead(); // 用栈来存储数据 Stack<HeroLink> stack = new Stack<>(); while (temp.next != null) { stack.push(temp.next); //压入栈中 temp = temp.next; } // 打印栈 while (stack.size() > 0) { System.out.println(stack.pop()); } }

测试结果