"本文主要讲解了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;
}
```
这些代码实现了上述的三个面试题目的解决方案。通过理解单链表的特性和操作，可以有效地解决这些问题，这对于面试和实际开发都是非常有帮助的。在实际应用中，掌握链表的操作和算法是提升程序性能和解决问题的关键。
我的内容管理
展开
