Java链表面试题解析：统计节点、找倒数K节点与逆转链表

"本文主要讲解了Java中单链表的相关数据结构与算法，涵盖了在新浪和腾讯面试中常见的几个问题，包括统计链表中有效节点的个数、获取倒数第K个元素以及单向链表的逆转。文章提供了详细的题目分析、代码实现和测试用例。" 在Java数据结构中，单链表是一种基础且重要的结构，通常用于存储线性序列的数据。它由一系列节点组成，每个节点包含数据和指向下一个节点的引用。单链表的特点是只能通过前一个节点来访问当前节点，因此插入和删除操作相对简单，但查找效率较低。 1. 统计链表中有效节点的个数（不含头结点）【新浪】 解决这个问题的关键在于从头结点开始遍历链表，但不包括头结点本身。可以初始化一个计数器为0，然后遍历链表，每次遇到一个节点时，计数器加1，直到到达链表末尾。最后返回计数器的值即可。 2. 获取链表中倒数第K个元素【新浪】 先计算整个链表的长度，然后从头结点开始，逆向遍历到第K个元素。这里要注意的是，如果K从0开始计算，那么实际位置应为length - K，而如果K从1开始，则应为length - K + 1。 3. 单向链表的逆转【腾讯】 逆转单链表需要创建一个新的头结点，并将原链表的节点依次连接到新头结点后面。具体操作是在遍历原链表的过程中，每次将当前节点的next指向前一个节点，最后将原头结点指向新头结点的下一个节点，完成逆转。 以下是一些关键的Java代码实现： ```java // 定义HeroNode类，表示链表节点 class HeroNode { int data; HeroNode next; // 构造函数 HeroNode(int data) { this.data = data; this.next = null; } } // 第一题：统计有效节点个数 public static int getLength(HeroNode headHeroNode) { int count = 0; if (headHeroNode.next == null) return 0; HeroNode temp = headHeroNode.next; while (temp != null) { count++; temp = temp.next; } return count; } // 第二题：查找倒数第k个结点 public static void find(HeroNode head, int index) { if (head.next == null) { System.out.println("英雄榜为空！"); return; } HeroNode temp = head; int size = getLength(head); if (index > size || index < 0) { System.out.println("输入的K不合法！"); } else { for (int i = 1; i <= size - index; i++) { temp = temp.next; } System.out.println("倒数第" + index + "个结点是：" + temp.data); } } // 第三题：逆转单链表 public static HeroNode reverse(HeroNode oldHead) { if (oldHead == null || oldHead.next == null) return oldHead; HeroNode newHead = new HeroNode(0); HeroNode temp = oldHead; while (temp != null) { HeroNode nextTemp = temp.next; temp.next = newHead.next; newHead.next = temp; temp = nextTemp; } oldHead = newHead.next; return oldHead; } ``` 这些代码实现了上述的三个面试题目的解决方案。通过理解单链表的特性和操作，可以有效地解决这些问题，这对于面试和实际开发都是非常有帮助的。在实际应用中，掌握链表的操作和算法是提升程序性能和解决问题的关键。