- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
java解法
- 解题思路
- 这段代码实现的是链表的环检测问题，具体来说，给定一个链表的起始节点及其后续节点信息，我们需要判断链表是否存在环，并输出环的入口节点的值。
问题背景：
给定一个链表，每个节点包含两个信息：
节点的值。
下一个节点的标识符（或标记为 -1，表示链表结束）。
输入数据包含链表的起始节点、节点数目及每个节点的详细信息。
需要找出链表中的环的入口节点，如果存在环。
思路：
使用哈希表存储节点信息：我们使用一个 Map 来保存每个节点的值和指向下一个节点的标识符。
快慢指针法：
使用两个指针 slow 和 fast，slow 每次移动一步，fast 每次移动两步。
如果链表存在环，两个指针最终会相遇。
在快慢指针相遇后，重新设置一个指针从起始节点开始，每次一步一步前进，另一个指针不动，最终会在环的入口节点相遇。
输出环的入口节点的值。
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static class Node {
int val;
String next;
public Node(int val, String next) {
this.val = val;
this.next = next;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Map<String, Node> map = new HashMap<>();
String[] input = sc.nextLine().split(" ");
String start = input[0];
int n = Integer.parseInt(input[1]);
for (int i = 0; i < n; i++) {
String[] nodeInfo = sc.nextLine().split(" ");
map.put(nodeInfo[0], new Node(Integer.parseInt(nodeInfo[1]), nodeInfo[2]));
}
String slow = start, fast = start;
while (!fast.equals("-1") && !map.get(fast).next.equals("-1")) {
slow = map.get(slow).next;
fast = map.get(map.get(fast).next).next;
}
System.out.println(map.get(slow).val);
}
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
C++解法
- 解题思路
- 这段代码解决的问题是 链表的环检测，并找到环的入口节点，通过使用 快慢指针法 来实现。
具体思路如下：
链表的表示：
每个节点包含 data（节点的值）和 next（指向下一个节点的地址或 -1，表示链表结束）。
使用哈希表（unordered_map）存储链表中每个节点的地址和节点数据。
环检测和寻找环的入口节点：
使用 快慢指针（slow 和 fast），其中 slow 每次走一步，fast 每次走两步。
如果链表中存在环，slow 和 fast 指针最终会相遇。
在相遇之后，重新设置一个指针从链表的起始节点开始，每次一步一步前进，另一个指针不动，最终会在环的入口处相遇。
输出环的入口节点的值。
主要步骤：
读取输入，构建链表。
使用快慢指针检测环并找到入口节点。
#include
#include
#include
using namespace std;
// 链表节点结构体
struct Node {
int data; // 节点的值
string next; // 下一节点的地址（字符串）
// 默认构造函数
Node() : data(0), next("") {}
// 带参数的构造函数
Node(int data, const string& next) : data(data), next(next) {}
};
// 查找环的入口节点
void find_middle_node() {
unordered_map nodes; // 哈希表，用于存储每个节点
string first; // 链表的起始节点地址
int n; // 节点的数量
// 读取起始节点地址和节点数量
cin >> first >> n;
cin.ignore(); // 忽略行尾的换行符
// 读取每个节点的信息并存入哈希表
for (int i = 0; i < n; ++i) {
string addr, next_addr; // 当前节点地址和下一节点的地址
int data; // 当前节点的值
cin >> addr >> data >> next_addr;
nodes[addr] = Node(data, next_addr); // 将节点信息存入哈希表
}
// 快慢指针初始化，分别从起始节点开始
string slow = first, fast = first;
// 快慢指针法：快指针每次走两步，慢指针每次走一步
// 如果有环，快指针和慢指针最终会相遇
while (fast != "-1" && nodes[fast].next != "-1") {
slow = nodes[slow].next; // 慢指针走一步
fast = nodes[nodes[fast].next].next; // 快指针走两步
}
// 输出慢指针所在的节点数据，作为环的入口节点
cout << nodes[slow].data << endl;
}
// 主函数，执行链表环入口查找
int main() {
find_middle_node(); // 调用函数查找环的入口节点
return 0;
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
C解法
更新中
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
JS解法
节点的地址。
节点的值。
指向下一个节点的地址，若指向 -1 表示链表结束。
我们可以通过以下步骤来解决问题：
构建链表：使用一个哈希映射（Map）存储每个节点的地址和节点对象。每个节点对象包含节点的值和指向下一个节点的地址。
遍历链表：从给定的起始节点开始，按照链表的连接关系遍历链表，将节点按顺序存入数组。
找中间节点：找到链表的中间节点。可以通过计算链表长度的一半索引来获得中间节点，并返回它的值。
class Node {
constructor(data, next) {
this.data = data;
this.next = next;
}
}
function findMiddleNode(start, nodes) {
let list = [];
let current = start;
while (current !== '-1') {
const node = nodes.get(current);
list.push(node);
current = node.next;
}
return list[Math.floor(list.length / 2)].data;
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('', (firstLine) => {
const [start, count] = firstLine.split(" ");
const nodes = new Map();
let linesRead = 0;
rl.on('line', (line) => {
const [address, data, next] = line.split(" ");
nodes.set(address, new Node(parseInt(data), next));
linesRead++;
if (linesRead === parseInt(count)) {
console.log(findMiddleNode(start, nodes));
rl.close();
}
});
});
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：