831 lines
34 KiB
HTML
831 lines
34 KiB
HTML
<!DOCTYPE html>
|
||
<html lang="zh-CN">
|
||
<head>
|
||
<meta charset="UTF-8">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
||
<title>142. Linked List Cycle II — Floyd 双阶段算法可视化</title>
|
||
<link rel="stylesheet" href="../shared/style.css">
|
||
<style>
|
||
/* ── Base / Fallback if shared.css absent ── */
|
||
:root {
|
||
--bg: #0f1117; --card: #181b25; --border: #2a2e3a;
|
||
--fg: #e4e6ed; --muted: #8b8fa3; --accent: #6c8cff;
|
||
--slow: #3b82f6; --fast: #ef4444; --ptr1: #10b981; --ptr2: #a855f7;
|
||
--meeting: #f59e0b; --entry: #fbbf24; --code-bg: #0d0f14;
|
||
--phase1: #3b82f6; --phase2: #10b981;
|
||
}
|
||
* { margin: 0; padding: 0; box-sizing: border-box; }
|
||
body {
|
||
background: var(--bg); color: var(--fg);
|
||
font-family: -apple-system, "PingFang SC", "Microsoft YaHei", sans-serif;
|
||
line-height: 1.6;
|
||
}
|
||
#app {
|
||
max-width: 900px; margin: 0 auto; padding: 24px 16px 60px;
|
||
}
|
||
h1 { font-size: 1.55rem; font-weight: 700; letter-spacing: -0.02em; }
|
||
.subtitle { color: var(--muted); font-size: 0.92rem; margin-top: 2px; }
|
||
.badge {
|
||
display: inline-block; background: #1e2333; color: var(--accent);
|
||
border: 1px solid var(--border); border-radius: 6px;
|
||
padding: 1px 8px; font-size: 0.78rem; font-weight: 600;
|
||
}
|
||
|
||
/* ── Cards ── */
|
||
.card {
|
||
background: var(--card); border: 1px solid var(--border);
|
||
border-radius: 12px; padding: 16px; margin-top: 14px;
|
||
}
|
||
.card-title {
|
||
font-size: 0.82rem; font-weight: 600; color: var(--muted);
|
||
text-transform: uppercase; letter-spacing: 0.06em; margin-bottom: 10px;
|
||
}
|
||
|
||
/* ── Example Buttons & Input ── */
|
||
.top-bar { display: flex; flex-wrap: wrap; gap: 8px; align-items: center; margin-top: 14px; }
|
||
.example-btn {
|
||
background: #1e2333; color: var(--fg); border: 1px solid var(--border);
|
||
border-radius: 8px; padding: 6px 14px; font-size: 0.82rem;
|
||
cursor: pointer; transition: all 0.15s;
|
||
}
|
||
.example-btn:hover { border-color: var(--accent); color: var(--accent); }
|
||
.example-btn.active { background: var(--accent); color: #fff; border-color: var(--accent); }
|
||
.input-group {
|
||
display: flex; gap: 6px; align-items: center; margin-left: auto;
|
||
}
|
||
.input-group input {
|
||
background: #12141c; color: var(--fg); border: 1px solid var(--border);
|
||
border-radius: 8px; padding: 6px 12px; font-size: 0.82rem;
|
||
width: 240px; outline: none; font-family: "SF Mono", "Fira Code", monospace;
|
||
}
|
||
.input-group input:focus { border-color: var(--accent); }
|
||
.input-group button {
|
||
background: var(--accent); color: #fff; border: none; border-radius: 8px;
|
||
padding: 6px 14px; font-size: 0.82rem; cursor: pointer; font-weight: 600;
|
||
}
|
||
|
||
/* ── Pipeline ── */
|
||
.pipeline {
|
||
display: flex; gap: 0; margin-top: 14px;
|
||
background: #12141c; border-radius: 10px; overflow: hidden;
|
||
border: 1px solid var(--border);
|
||
}
|
||
.pipeline-stage {
|
||
flex: 1; text-align: center; padding: 9px 6px; font-size: 0.78rem;
|
||
font-weight: 600; color: var(--muted); position: relative;
|
||
transition: all 0.25s;
|
||
}
|
||
.pipeline-stage.active { color: #fff; }
|
||
.pipeline-stage.active[data-color="blue"] { background: var(--phase1); }
|
||
.pipeline-stage.active[data-color="amber"] { background: #b47d09; }
|
||
.pipeline-stage.active[data-color="green"] { background: var(--phase2); }
|
||
.pipeline-stage.active[data-color="final"] { background: #059669; }
|
||
.pipeline-stage + .pipeline-stage { border-left: 1px solid var(--border); }
|
||
|
||
/* ── Hint ── */
|
||
.hint-box {
|
||
margin-top: 14px; padding: 10px 16px; border-radius: 10px;
|
||
background: #1b1f2e; border-left: 4px solid var(--accent);
|
||
font-size: 0.88rem; min-height: 40px; display: flex;
|
||
align-items: center; gap: 8px;
|
||
}
|
||
.hint-box .icon { font-size: 1.05rem; }
|
||
.hint-box .phase-tag {
|
||
display: inline-block; border-radius: 4px; padding: 1px 7px;
|
||
font-size: 0.72rem; font-weight: 700; color: #fff; flex-shrink: 0;
|
||
}
|
||
.hint-box .phase-tag.p1 { background: var(--phase1); }
|
||
.hint-box .phase-tag.p2 { background: var(--phase2); }
|
||
.hint-box .phase-tag.done { background: #059669; }
|
||
|
||
/* ── Visualisation SVG ── */
|
||
.viz-card { padding: 0; overflow: hidden; }
|
||
#viz-svg {
|
||
width: 100%; height: auto; display: block;
|
||
}
|
||
|
||
/* ── SVG styles ── */
|
||
.node-rect {
|
||
rx: 8; ry: 8; stroke-width: 2; fill: #1e2333; stroke: var(--border);
|
||
transition: stroke 0.3s, fill 0.3s;
|
||
}
|
||
.node-rect.meeting { fill: #2a2410; stroke: var(--meeting); stroke-width: 2.5; }
|
||
.node-rect.entry { fill: #2a2410; stroke: var(--entry); stroke-width: 2.5; }
|
||
.node-rect.both { fill: #2d2a10; stroke: var(--meeting); stroke-width: 2.5; }
|
||
.node-val { fill: #e4e6ed; font-size: 16px; font-weight: 700; text-anchor: middle; dominant-baseline: central; }
|
||
.node-idx { fill: var(--muted); font-size: 10px; text-anchor: middle; dominant-baseline: auto; }
|
||
|
||
.arrow-line { stroke: #4a4f63; stroke-width: 2; fill: none; }
|
||
.cycle-line { stroke: var(--meeting); stroke-width: 2.2; fill: none; stroke-dasharray: 7 4; }
|
||
.null-line { stroke: #4a4f63; stroke-width: 2; fill: none; }
|
||
|
||
.ptr-label {
|
||
font-size: 11px; font-weight: 700; text-anchor: middle; dominant-baseline: central;
|
||
}
|
||
.ptr-badge-rect { rx: 4; ry: 4; }
|
||
|
||
/* ── Controls ── */
|
||
.controls {
|
||
display: flex; align-items: center; justify-content: center;
|
||
gap: 8px; margin-top: 12px;
|
||
}
|
||
.ctrl-btn {
|
||
background: #1e2333; color: var(--fg); border: 1px solid var(--border);
|
||
border-radius: 8px; width: 38px; height: 34px; font-size: 1rem;
|
||
cursor: pointer; display: flex; align-items: center; justify-content: center;
|
||
transition: all 0.15s;
|
||
}
|
||
.ctrl-btn:hover { border-color: var(--accent); color: var(--accent); }
|
||
.ctrl-btn:disabled { opacity: 0.35; cursor: default; }
|
||
.ctrl-btn.playing { background: var(--accent); color: #fff; border-color: var(--accent); }
|
||
.step-counter { font-size: 0.82rem; color: var(--muted); min-width: 70px; text-align: center; }
|
||
|
||
/* ── Detail Panel ── */
|
||
.detail-body { font-size: 0.88rem; line-height: 1.7; white-space: pre-wrap; }
|
||
.detail-body .math {
|
||
background: #12141c; border-radius: 6px; padding: 8px 12px;
|
||
margin: 6px 0; font-family: "SF Mono", "Fira Code", Consolas, monospace;
|
||
font-size: 0.82rem; color: #c5cae0; display: block;
|
||
}
|
||
|
||
/* ── Result Panel ── */
|
||
.result-body { font-size: 0.92rem; }
|
||
.result-body .val { color: var(--entry); font-weight: 700; font-size: 1.1rem; }
|
||
.result-body .null-val { color: var(--muted); font-style: italic; }
|
||
.result-hidden { display: none; }
|
||
|
||
/* ── Code Panel ── */
|
||
.code-panel { background: var(--code-bg); }
|
||
.code-panel pre {
|
||
margin: 0; overflow-x: auto; font-size: 0.82rem; line-height: 1.65;
|
||
font-family: "SF Mono", "Fira Code", Consolas, monospace;
|
||
color: #c5cae0;
|
||
}
|
||
.code-panel .kw { color: #c678dd; }
|
||
.code-panel .fn { color: #61afef; }
|
||
.code-panel .cm { color: #5c6370; font-style: italic; }
|
||
.code-panel .st { color: #98c379; }
|
||
.code-panel .num { color: #d19a66; }
|
||
.code-panel .op { color: #56b6c2; }
|
||
.code-panel .hl-line {
|
||
background: rgba(108,140,255,0.08); display: block;
|
||
margin: 0 -16px; padding: 0 16px; border-left: 3px solid var(--accent);
|
||
}
|
||
|
||
/* ── Pulse Animation ── */
|
||
@keyframes entryPulse {
|
||
0%, 100% { stroke-opacity: 1; filter: drop-shadow(0 0 4px rgba(251,191,36,0.4)); }
|
||
50% { stroke-opacity: 0.7; filter: drop-shadow(0 0 10px rgba(251,191,36,0.7)); }
|
||
}
|
||
.node-rect.entry { animation: entryPulse 1.4s ease-in-out infinite; }
|
||
|
||
@keyframes meetingPulse {
|
||
0%, 100% { stroke-opacity: 1; }
|
||
50% { stroke-opacity: 0.6; }
|
||
}
|
||
.node-rect.meeting { animation: meetingPulse 1.2s ease-in-out infinite; }
|
||
|
||
/* ── Responsive ── */
|
||
@media (max-width: 640px) {
|
||
.top-bar { flex-direction: column; align-items: stretch; }
|
||
.input-group { margin-left: 0; }
|
||
.input-group input { flex: 1; width: auto; }
|
||
}
|
||
</style>
|
||
</head>
|
||
<body>
|
||
<div id="app">
|
||
<!-- Title -->
|
||
<h1>142. Linked List Cycle II</h1>
|
||
<p class="subtitle">Floyd 双阶段算法 — 检测环 & 找到入口 <span class="badge">Medium #026</span></p>
|
||
|
||
<!-- Examples & Input -->
|
||
<div class="top-bar">
|
||
<button class="example-btn active" data-idx="0">示例1: [3,2,0,-4] pos=1</button>
|
||
<button class="example-btn" data-idx="1">示例2: [1,2] pos=0</button>
|
||
<button class="example-btn" data-idx="2">示例3: [1] pos=-1</button>
|
||
<div class="input-group">
|
||
<input id="custom-input" placeholder='head=[3,2,0,-4], pos=1'>
|
||
<button id="run-btn">运行</button>
|
||
</div>
|
||
</div>
|
||
|
||
<!-- Pipeline -->
|
||
<div class="pipeline">
|
||
<div class="pipeline-stage active" data-color="blue" id="pipe-0">阶段1: 检测环</div>
|
||
<div class="pipeline-stage" data-color="amber" id="pipe-1">相遇</div>
|
||
<div class="pipeline-stage" data-color="green" id="pipe-2">阶段2: 找入口</div>
|
||
<div class="pipeline-stage" data-color="final" id="pipe-3">结果</div>
|
||
</div>
|
||
|
||
<!-- Hint -->
|
||
<div class="hint-box" id="hint-box">
|
||
<span class="icon">💡</span>
|
||
<span id="hint-text">点击示例或输入数据开始</span>
|
||
</div>
|
||
|
||
<!-- Visualisation -->
|
||
<div class="card viz-card">
|
||
<svg id="viz-svg" viewBox="0 0 820 280" xmlns="http://www.w3.org/2000/svg">
|
||
<defs>
|
||
<marker id="arrowGray" viewBox="0 0 10 10" refX="9" refY="5"
|
||
markerWidth="7" markerHeight="7" orient="auto-start-reverse">
|
||
<path d="M 0 1 L 9 5 L 0 9 z" fill="#4a4f63"/>
|
||
</marker>
|
||
<marker id="arrowCycle" viewBox="0 0 10 10" refX="9" refY="5"
|
||
markerWidth="7" markerHeight="7" orient="auto-start-reverse">
|
||
<path d="M 0 1 L 9 5 L 0 9 z" fill="#f59e0b"/>
|
||
</marker>
|
||
<marker id="arrowNull" viewBox="0 0 10 10" refX="9" refY="5"
|
||
markerWidth="7" markerHeight="7" orient="auto-start-reverse">
|
||
<path d="M 0 1 L 9 5 L 0 9 z" fill="#4a4f63"/>
|
||
</marker>
|
||
</defs>
|
||
<g id="svg-layer"></g>
|
||
</svg>
|
||
</div>
|
||
|
||
<!-- Controls -->
|
||
<div class="controls">
|
||
<button class="ctrl-btn" id="btn-first" title="第一步">⏮</button>
|
||
<button class="ctrl-btn" id="btn-prev" title="上一步">◀</button>
|
||
<button class="ctrl-btn" id="btn-play" title="播放/暂停">▶</button>
|
||
<button class="ctrl-btn" id="btn-next" title="下一步">▶</button>
|
||
<button class="ctrl-btn" id="btn-last" title="最后一步">⏭</button>
|
||
<span class="step-counter" id="step-counter">0 / 0</span>
|
||
</div>
|
||
|
||
<!-- Detail -->
|
||
<div class="card">
|
||
<div class="card-title">📋 详细说明</div>
|
||
<div class="detail-body" id="detail-body">等待开始…</div>
|
||
</div>
|
||
|
||
<!-- Result -->
|
||
<div class="card result-hidden" id="result-card">
|
||
<div class="card-title">✅ 结果</div>
|
||
<div class="result-body" id="result-body"></div>
|
||
</div>
|
||
|
||
<!-- Code -->
|
||
<div class="card code-panel">
|
||
<div class="card-title">🐍 Python 代码</div>
|
||
<pre id="code-block"><span class="kw">class</span> <span class="fn">Solution</span>:
|
||
<span class="kw">def</span> <span class="fn">detectCycle</span>(self, head):
|
||
<span class="kw">if not</span> head <span class="kw">or not</span> head.next:
|
||
<span class="kw">return</span> <span class="num">None</span>
|
||
slow <span class="op">=</span> fast <span class="op">=</span> head
|
||
<span class="cm"> # Phase 1: detect cycle</span>
|
||
<span class="kw">while</span> fast <span class="kw">and</span> fast.next:
|
||
slow <span class="op">=</span> slow.next
|
||
fast <span class="op">=</span> fast.next.next
|
||
<span class="kw">if</span> slow <span class="op">==</span> fast:
|
||
<span class="cm"> # Phase 2: find entry</span>
|
||
ptr <span class="op">=</span> head
|
||
<span class="kw">while</span> ptr <span class="op">!=</span> slow:
|
||
ptr <span class="op">=</span> ptr.next
|
||
slow <span class="op">=</span> slow.next
|
||
<span class="kw">return</span> ptr
|
||
<span class="kw">return</span> <span class="num">None</span></pre>
|
||
</div>
|
||
</div>
|
||
|
||
<script src="../shared/algo-viz.js"></script>
|
||
<script>
|
||
(function() {
|
||
'use strict';
|
||
|
||
/* ═══════════════════════════════════════════
|
||
StepController – fallback if shared JS absent
|
||
═══════════════════════════════════════════ */
|
||
const StepController = (typeof window.StepController !== 'undefined')
|
||
? window.StepController
|
||
: class {
|
||
constructor() {
|
||
this.steps = []; this.idx = 0; this.playing = false; this.timer = null;
|
||
this.speed = 1400; this.onStep = null; this.onPlay = null;
|
||
}
|
||
setSteps(s) { this.steps = s; this.idx = 0; this._emit(); }
|
||
cur() { return this.steps[this.idx]; }
|
||
total(){ return this.steps.length; }
|
||
goTo(i){ this.idx = Math.max(0, Math.min(i, this.steps.length-1)); this._emit(); }
|
||
next() { if(this.idx < this.steps.length-1){ this.idx++; this._emit(); } else this.pause(); }
|
||
prev() { if(this.idx > 0){ this.idx--; this._emit(); } }
|
||
first(){ this.goTo(0); }
|
||
last() { this.goTo(this.steps.length-1); }
|
||
play() {
|
||
if(this.playing) return; this.playing = true; this._playEmit();
|
||
this.timer = setInterval(()=> this.next(), this.speed);
|
||
}
|
||
pause(){
|
||
this.playing = false; clearInterval(this.timer); this._playEmit();
|
||
}
|
||
toggle() { this.playing ? this.pause() : this.play(); }
|
||
_emit() { if(this.onStep) this.onStep(this.idx, this.cur()); }
|
||
_playEmit(){ if(this.onPlay) this.onPlay(this.playing); }
|
||
};
|
||
|
||
/* ═══════════════════════════════════════════
|
||
Constants
|
||
═══════════════════════════════════════════ */
|
||
const NW = 66, NH = 44, GAP = 58; // node width / height / gap
|
||
const SVG_W = 820, SVG_H = 280;
|
||
const NODE_Y = 80; // centre-Y for top row
|
||
const PTR_Y = NODE_Y + NH/2 + 22; // pointer label Y
|
||
const CYCLE_BULGE = 70; // how far the cycle arc dips down
|
||
|
||
const EXAMPLES = [
|
||
{ values: [3, 2, 0, -4], pos: 1 },
|
||
{ values: [1, 2], pos: 0 },
|
||
{ values: [1], pos: -1 }
|
||
];
|
||
|
||
/* ═══════════════════════════════════════════
|
||
Parse input: "head=[3,2,0,-4], pos=1"
|
||
═══════════════════════════════════════════ */
|
||
function parseInput(str) {
|
||
const m1 = str.match(/head\s*=\s*\[([^\]]*)\]/i);
|
||
const m2 = str.match(/pos\s*=\s*(-?\d+)/i);
|
||
if (!m1 || !m2) return null;
|
||
const values = m1[1].split(',').map(s => {
|
||
const v = s.trim(); return v === '' ? 0 : Number(v);
|
||
});
|
||
const pos = parseInt(m2[1], 10);
|
||
return { values, pos };
|
||
}
|
||
|
||
/* ═══════════════════════════════════════════
|
||
Generate Steps
|
||
═══════════════════════════════════════════ */
|
||
function generateSteps(values, pos) {
|
||
const n = values.length;
|
||
const next = [];
|
||
for (let i = 0; i < n - 1; i++) next[i] = i + 1;
|
||
next[n - 1] = pos >= 0 ? pos : -1;
|
||
|
||
const steps = [];
|
||
const hasCycle = pos >= 0 && n > 0;
|
||
|
||
// ──── No cycle or empty ────
|
||
if (n === 0) {
|
||
steps.push({
|
||
phase: 'result', pipelineStage: 3,
|
||
slow: -1, fast: -1, ptr1: -1, ptr2: -1,
|
||
meetingIdx: -1, entryIdx: -1,
|
||
hint: '链表为空', phaseTag: 'done',
|
||
detail: '链表为空，直接返回 null。',
|
||
resultVal: null
|
||
});
|
||
return steps;
|
||
}
|
||
|
||
// ──── Step 0: Init ────
|
||
steps.push({
|
||
phase: 1, pipelineStage: 0,
|
||
slow: 0, fast: 0, ptr1: -1, ptr2: -1,
|
||
meetingIdx: -1, entryIdx: -1,
|
||
hint: `初始化: slow = fast = head (节点 ${values[0]})`,
|
||
phaseTag: 'p1',
|
||
detail: 'Floyd 算法开始：慢指针 slow 每次走 1 步，快指针 fast 每次走 2 步。\n若链表有环，二者必在环内相遇。'
|
||
});
|
||
|
||
if (!hasCycle) {
|
||
// fast can't move
|
||
steps.push({
|
||
phase: 'result', pipelineStage: 3,
|
||
slow: 0, fast: 0, ptr1: -1, ptr2: -1,
|
||
meetingIdx: -1, entryIdx: -1,
|
||
hint: `${n === 1 ? 'fast.next 为空' : 'fast 到达链表末尾'}，无环`,
|
||
phaseTag: 'done',
|
||
detail: n === 1
|
||
? '链表仅有一个节点，head.next 为 null。fast 无法前进，说明链表无环。\n返回 null。'
|
||
: `快指针 fast 到达链表末尾 (null)，说明链表无环。\n返回 null。`,
|
||
resultVal: null
|
||
});
|
||
return steps;
|
||
}
|
||
|
||
// ──── Phase 1: detect cycle ────
|
||
let slow = 0, fast = 0, round = 0;
|
||
const safetyLimit = n * n + 10;
|
||
|
||
while (round++ < safetyLimit) {
|
||
const ns = next[slow];
|
||
const nf1 = next[fast];
|
||
const nf2 = nf1 >= 0 ? next[nf1] : -1;
|
||
if (nf2 === -1) break; // shouldn't happen if cycle exists
|
||
slow = ns; fast = nf2;
|
||
|
||
if (slow === fast) {
|
||
// Meeting!
|
||
const distA = distFromHead(next, slow);
|
||
const cycLen = cycleLen(next, pos, n);
|
||
const distB = distInCycle(next, pos, slow);
|
||
const distC = cycLen - distB;
|
||
const k = Math.round((distA + distB) / cycLen); // how many extra laps fast made
|
||
steps.push({
|
||
phase: 1, pipelineStage: 1,
|
||
slow, fast, ptr1: -1, ptr2: -1,
|
||
meetingIdx: slow, entryIdx: -1,
|
||
hint: `slow 与 fast 在节点 ${values[slow]} 相遇！确认有环`,
|
||
phaseTag: 'p1',
|
||
detail:
|
||
`slow 每次走 1 步，fast 每次走 2 步，在节点 ${values[slow]} 处相遇。\n` +
|
||
`此时 slow 走了 ${distA + distB} 步（a=${distA}, b=${distB}），fast 走了 ${(distA + distB) * 2} 步。\n` +
|
||
`<span class="math">2(a+b) = a+b+kL → a = kL - b = (k-1)L + (L-b)\n` +
|
||
`其中 a=${distA}, b=${distB}, L=${cycLen}, k=${k}\n` +
|
||
`a = ${k}×${cycLen} - ${distB} = ${k * cycLen - distB} ✓</span>\n` +
|
||
`结论：从 head 和相遇点同时每次走 1 步，必在环入口相遇！`
|
||
});
|
||
break;
|
||
} else {
|
||
steps.push({
|
||
phase: 1, pipelineStage: 0,
|
||
slow, fast, ptr1: -1, ptr2: -1,
|
||
meetingIdx: -1, entryIdx: -1,
|
||
hint: `slow → ${values[slow]}, fast → ${values[fast]}，未相遇`,
|
||
phaseTag: 'p1',
|
||
detail: `slow 走 1 步到节点 ${values[slow]}，fast 走 2 步到节点 ${values[fast]}。\nslow ≠ fast，继续移动。`
|
||
});
|
||
}
|
||
}
|
||
|
||
const meetingIdx = slow;
|
||
|
||
// ──── Phase 2: find entry ────
|
||
let ptr1 = 0, ptr2 = meetingIdx;
|
||
steps.push({
|
||
phase: 2, pipelineStage: 2,
|
||
slow: meetingIdx, fast: meetingIdx, ptr1, ptr2,
|
||
meetingIdx, entryIdx: -1,
|
||
hint: `阶段2开始: ptr1 = head (${values[0]}), ptr2 = 相遇点 (${values[meetingIdx]})`,
|
||
phaseTag: 'p2',
|
||
detail:
|
||
`进入阶段 2 — 找环入口\n` +
|
||
`ptr1 从 head 出发，ptr2 从相遇点出发，每次各走 1 步。\n` +
|
||
`由数学推导 a = kL - b，两者必然在环入口相遇。`
|
||
});
|
||
|
||
round = 0;
|
||
while (ptr1 !== ptr2 && round++ < safetyLimit) {
|
||
ptr1 = next[ptr1];
|
||
ptr2 = next[ptr2];
|
||
|
||
if (ptr1 === ptr2) {
|
||
steps.push({
|
||
phase: 2, pipelineStage: 2,
|
||
slow: meetingIdx, fast: meetingIdx, ptr1, ptr2,
|
||
meetingIdx, entryIdx: ptr1,
|
||
hint: `ptr1 与 ptr2 在节点 ${values[ptr1]} 相遇 → 环入口！`,
|
||
phaseTag: 'p2',
|
||
detail:
|
||
`ptr1 从 head 走到节点 ${values[ptr1]}，ptr2 从相遇点走到节点 ${values[ptr2]}。\n` +
|
||
`两者相遇，说明节点 ${values[ptr1]} 就是环的入口！\n` +
|
||
`<span class="math">入口索引 = ${pos}，值 = ${values[ptr1]}</span>`
|
||
});
|
||
} else {
|
||
steps.push({
|
||
phase: 2, pipelineStage: 2,
|
||
slow: meetingIdx, fast: meetingIdx, ptr1, ptr2,
|
||
meetingIdx, entryIdx: -1,
|
||
hint: `ptr1 → ${values[ptr1]}, ptr2 → ${values[ptr2]}，未相遇`,
|
||
phaseTag: 'p2',
|
||
detail: `ptr1 走 1 步到 ${values[ptr1]}，ptr2 走 1 步到 ${values[ptr2]}，继续前进。`
|
||
});
|
||
}
|
||
}
|
||
|
||
// ──── Result ────
|
||
steps.push({
|
||
phase: 'result', pipelineStage: 3,
|
||
slow: meetingIdx, fast: meetingIdx, ptr1, ptr2,
|
||
meetingIdx, entryIdx: ptr1,
|
||
hint: `环入口节点: ${values[ptr1]} (索引 ${pos})`,
|
||
phaseTag: 'done',
|
||
detail:
|
||
`检测到环，入口为节点 ${values[ptr1]}（索引 ${pos}）。\n` +
|
||
`时间复杂度 O(n)，空间复杂度 O(1)。\n` +
|
||
`<span class="math">detectCycle → 节点 ${values[ptr1]}</span>`,
|
||
resultVal: { idx: ptr1, val: values[ptr1] }
|
||
});
|
||
|
||
return steps;
|
||
}
|
||
|
||
/* ── Helpers for step generation ── */
|
||
function distFromHead(nextArr, target) {
|
||
let d = 0, cur = 0;
|
||
const visited = new Set();
|
||
while (cur !== target && !visited.has(cur)) { visited.add(cur); cur = nextArr[cur]; d++; }
|
||
return cur === target ? d : -1;
|
||
}
|
||
function cycleLen(nextArr, entry, n) {
|
||
let len = 1, cur = nextArr[entry];
|
||
while (cur !== entry) { cur = nextArr[cur]; len++; }
|
||
return len;
|
||
}
|
||
function distInCycle(nextArr, entry, target) {
|
||
if (entry === target) return 0;
|
||
let d = 1, cur = nextArr[entry];
|
||
while (cur !== target) { cur = nextArr[cur]; d++; }
|
||
return d;
|
||
}
|
||
|
||
/* ═══════════════════════════════════════════
|
||
SVG Renderer
|
||
═══════════════════════════════════════════ */
|
||
function computePositions(n, pos) {
|
||
const totalW = n * NW + (n - 1) * GAP;
|
||
const sx = Math.max(50, (SVG_W - totalW) / 2);
|
||
const positions = [];
|
||
for (let i = 0; i < n; i++) {
|
||
positions.push({ x: sx + i * (NW + GAP), y: NODE_Y });
|
||
}
|
||
return positions;
|
||
}
|
||
|
||
function render(values, pos, step) {
|
||
const svg = document.getElementById('svg-layer');
|
||
const n = values.length;
|
||
if (n === 0) { svg.innerHTML = '<text x="410" y="140" text-anchor="middle" fill="#8b8fa3" font-size="16">空链表</text>'; return; }
|
||
|
||
const positions = computePositions(n, pos);
|
||
const hasCycle = pos >= 0;
|
||
let html = '';
|
||
|
||
// ── Forward arrows ──
|
||
for (let i = 0; i < n - 1; i++) {
|
||
const from = positions[i], to = positions[i + 1];
|
||
const x1 = from.x + NW + 1, y1 = from.y;
|
||
const x2 = to.x - 1, y2 = to.y;
|
||
html += `<line class="arrow-line" x1="${x1}" y1="${y1}" x2="${x2}" y2="${y2}" marker-end="url(#arrowGray)"/>`;
|
||
}
|
||
|
||
// ── Cycle arrow (curved) ──
|
||
if (hasCycle) {
|
||
const last = positions[n - 1];
|
||
const entry = positions[pos];
|
||
const lx = last.x + NW / 2, ly = last.y + NH / 2 + 2;
|
||
const ex = entry.x + NW / 2, ey = entry.y + NH / 2 + 2;
|
||
const midX = (lx + ex) / 2;
|
||
const bulge = CYCLE_BULGE + Math.abs(lx - ex) * 0.12;
|
||
const cy = ly + bulge;
|
||
html += `<path class="cycle-line" d="M${lx},${ly} C${lx},${cy} ${ex},${cy} ${ex},${ey}" marker-end="url(#arrowCycle)"/>`;
|
||
// Label
|
||
const labelY = cy + 4;
|
||
html += `<text x="${midX}" y="${labelY}" text-anchor="middle" fill="#f59e0b" font-size="11" font-weight="600">cycle</text>`;
|
||
} else {
|
||
// Null indicator after last node
|
||
const last = positions[n - 1];
|
||
const nx = last.x + NW + 12, ny = last.y;
|
||
html += `<line class="null-line" x1="${last.x + NW + 1}" y1="${ny}" x2="${nx + 20}" y2="${ny}" marker-end="url(#arrowNull)"/>`;
|
||
html += `<text x="${nx + 30}" y="${ny + 4}" fill="#ef4444" font-size="13" font-weight="700" text-anchor="start">null</text>`;
|
||
}
|
||
|
||
// ── Nodes ──
|
||
for (let i = 0; i < n; i++) {
|
||
const p = positions[i];
|
||
let cls = 'node-rect';
|
||
const isMeeting = step.meetingIdx === i;
|
||
const isEntry = step.entryIdx === i;
|
||
if (isMeeting && isEntry) cls += ' both';
|
||
else if (isEntry) cls += ' entry';
|
||
else if (isMeeting) cls += ' meeting';
|
||
|
||
html += `<rect class="${cls}" x="${p.x}" y="${p.y - NH/2}" width="${NW}" height="${NH}"/>`;
|
||
html += `<text class="node-val" x="${p.x + NW/2}" y="${p.y}">${values[i]}</text>`;
|
||
html += `<text class="node-idx" x="${p.x + NW/2}" y="${p.y - NH/2 - 5}">idx${i}</text>`;
|
||
}
|
||
|
||
// ── Pointer badges ──
|
||
const badgeH = 17, badgeR = 4;
|
||
const activePointers = [];
|
||
|
||
if (step.phase === 1 || step.phase === 'result') {
|
||
if (step.slow >= 0) activePointers.push({ idx: step.slow, label: 'slow', color: 'var(--slow)', emoji: '🐢' });
|
||
if (step.fast >= 0) activePointers.push({ idx: step.fast, label: 'fast', color: 'var(--fast)', emoji: '🐇' });
|
||
}
|
||
if (step.phase === 2 || step.phase === 'result') {
|
||
if (step.ptr1 >= 0) activePointers.push({ idx: step.ptr1, label: 'ptr1', color: 'var(--ptr1)', emoji: '🟢' });
|
||
if (step.ptr2 >= 0) activePointers.push({ idx: step.ptr2, label: 'ptr2', color: 'var(--ptr2)', emoji: '🟣' });
|
||
}
|
||
|
||
// Group by node index to handle overlaps
|
||
const byNode = {};
|
||
activePointers.forEach(p => {
|
||
if (!byNode[p.idx]) byNode[p.idx] = [];
|
||
byNode[p.idx].push(p);
|
||
});
|
||
|
||
Object.keys(byNode).forEach(idxStr => {
|
||
const idx = parseInt(idxStr);
|
||
const ptrs = byNode[idx];
|
||
const p = positions[idx];
|
||
const centerX = p.x + NW / 2;
|
||
const totalW = ptrs.length * 42 - 6;
|
||
const startX = centerX - totalW / 2;
|
||
|
||
ptrs.forEach((ptr, pi) => {
|
||
const bx = startX + pi * 42;
|
||
const by = PTR_Y + (idx === step.meetingIdx && idx !== step.entryIdx ? -22 : 0);
|
||
const label = ptr.emoji + ' ' + ptr.label;
|
||
const tw = label.length * 6.5 + 8;
|
||
html += `<rect class="ptr-badge-rect" x="${bx}" y="${by - badgeH/2}" width="${tw}" height="${badgeH}" fill="${ptr.color}" fill-opacity="0.18" stroke="${ptr.color}" stroke-width="1"/>`;
|
||
html += `<text class="ptr-label" x="${bx + tw/2}" y="${by}" fill="${ptr.color}">${label}</text>`;
|
||
// Small connecting line from badge to node
|
||
html += `<line x1="${bx + tw/2}" y1="${by - badgeH/2}" x2="${bx + tw/2}" y2="${p.y + NH/2}" stroke="${ptr.color}" stroke-width="1" stroke-opacity="0.5" stroke-dasharray="3 2"/>`;
|
||
});
|
||
});
|
||
|
||
// ── Meeting / Entry markers ──
|
||
if (step.meetingIdx >= 0 && step.meetingIdx !== step.entryIdx) {
|
||
const p = positions[step.meetingIdx];
|
||
html += `<text x="${p.x + NW/2}" y="${p.y - NH/2 - 18}" text-anchor="middle" fill="#f59e0b" font-size="11" font-weight="700">⭐ 相遇点</text>`;
|
||
}
|
||
if (step.entryIdx >= 0) {
|
||
const p = positions[step.entryIdx];
|
||
const labelY = step.meetingIdx === step.entryIdx ? p.y - NH/2 - 30 : p.y - NH/2 - 18;
|
||
html += `<text x="${p.x + NW/2}" y="${labelY}" text-anchor="middle" fill="#fbbf24" font-size="11" font-weight="700">🎯 入口</text>`;
|
||
}
|
||
|
||
// ── Phase indicator in SVG corner ──
|
||
let phaseText = '', phaseColor = '';
|
||
if (step.phase === 1) { phaseText = 'PHASE 1: 检测环'; phaseColor = 'var(--phase1)'; }
|
||
else if (step.phase === 2) { phaseText = 'PHASE 2: 找入口'; phaseColor = 'var(--phase2)'; }
|
||
else if (step.phase === 'result') { phaseText = 'RESULT'; phaseColor = '#059669'; }
|
||
if (phaseText) {
|
||
html += `<rect x="14" y="12" width="${phaseText.length * 8 + 16}" height="24" rx="5" fill="${phaseColor}" fill-opacity="0.15" stroke="${phaseColor}" stroke-width="1"/>`;
|
||
html += `<text x="22" y="28" fill="${phaseColor}" font-size="12" font-weight="700">${phaseText}</text>`;
|
||
}
|
||
|
||
svg.innerHTML = html;
|
||
}
|
||
|
||
/* ═══════════════════════════════════════════
|
||
UI Update
|
||
═══════════════════════════════════════════ */
|
||
function updatePipeline(stageIdx) {
|
||
for (let i = 0; i < 4; i++) {
|
||
const el = document.getElementById('pipe-' + i);
|
||
el.classList.toggle('active', i <= stageIdx);
|
||
}
|
||
}
|
||
|
||
function updateHint(step) {
|
||
const hintEl = document.getElementById('hint-text');
|
||
const box = document.getElementById('hint-box');
|
||
let tag = '';
|
||
if (step.phaseTag === 'p1') tag = '<span class="phase-tag p1">阶段1</span>';
|
||
if (step.phaseTag === 'p2') tag = '<span class="phase-tag p2">阶段2</span>';
|
||
if (step.phaseTag === 'done') tag = '<span class="phase-tag done">完成</span>';
|
||
hintEl.innerHTML = tag + ' ' + escHtml(step.hint);
|
||
}
|
||
|
||
function updateDetail(step) {
|
||
document.getElementById('detail-body').innerHTML = step.detail;
|
||
}
|
||
|
||
function updateResult(step) {
|
||
const card = document.getElementById('result-card');
|
||
const body = document.getElementById('result-body');
|
||
if (step.phase === 'result') {
|
||
card.classList.remove('result-hidden');
|
||
if (step.resultVal === null) {
|
||
body.innerHTML = '该链表没有环，返回 <span class="null-val">null</span>';
|
||
} else {
|
||
body.innerHTML = `环的入口节点: <span class="val">${step.resultVal.val}</span> (索引 ${step.resultVal.idx})`;
|
||
}
|
||
} else {
|
||
card.classList.add('result-hidden');
|
||
}
|
||
}
|
||
|
||
function updateCodeHighlight(step) {
|
||
const block = document.getElementById('code-block');
|
||
const spans = block.querySelectorAll('span');
|
||
// Remove old highlights
|
||
spans.forEach(s => s.classList.remove('hl-line'));
|
||
|
||
// Determine which logical lines to highlight
|
||
const lines = block.innerHTML.split('\n');
|
||
let hlLine = -1;
|
||
if (step.phase === 1 && step.pipelineStage === 0 && step.slow === 0 && step.fast === 0 && !step.meetingIdx && step.meetingIdx !== 0) {
|
||
hlLine = 4; // slow = fast = head
|
||
} else if (step.phase === 1 && step.pipelineStage === 0) {
|
||
hlLine = 7; // while fast
|
||
} else if (step.phase === 1 && step.pipelineStage === 1) {
|
||
hlLine = 10; // if slow == fast
|
||
} else if (step.phase === 2 && step.ptr1 === 0) {
|
||
hlLine = 13; // ptr = head
|
||
} else if (step.phase === 2) {
|
||
hlLine = 15; // while ptr != slow
|
||
} else if (step.phase === 'result' && step.resultVal !== null) {
|
||
hlLine = 17; // return ptr
|
||
} else if (step.phase === 'result') {
|
||
hlLine = 18; // return None
|
||
}
|
||
// Apply highlight (simple approach: mark the line)
|
||
if (hlLine >= 0 && hlLine < lines.length) {
|
||
if (!lines[hlLine].includes('hl-line')) {
|
||
lines[hlLine] = lines[hlLine].replace(/^(<span[^>]*>)/, '<span class="hl-line">');
|
||
}
|
||
block.innerHTML = lines.join('\n');
|
||
}
|
||
}
|
||
|
||
function updateStepCounter(cur, total) {
|
||
document.getElementById('step-counter').textContent = `${cur + 1} / ${total}`;
|
||
}
|
||
|
||
function updateControls(idx, total, playing) {
|
||
document.getElementById('btn-prev').disabled = idx <= 0;
|
||
document.getElementById('btn-first').disabled = idx <= 0;
|
||
document.getElementById('btn-next').disabled = idx >= total - 1;
|
||
document.getElementById('btn-last').disabled = idx >= total - 1;
|
||
const playBtn = document.getElementById('btn-play');
|
||
playBtn.textContent = playing ? '⏸' : '▶';
|
||
playBtn.classList.toggle('playing', playing);
|
||
}
|
||
|
||
function escHtml(s) {
|
||
return s.replace(/&/g,'&').replace(/</g,'<').replace(/>/g,'>');
|
||
}
|
||
|
||
/* ═══════════════════════════════════════════
|
||
Main Controller
|
||
═══════════════════════════════════════════ */
|
||
const sc = new StepController();
|
||
let currentValues = [], currentPos = -1;
|
||
|
||
function loadExample(idx) {
|
||
const ex = EXAMPLES[idx];
|
||
currentValues = ex.values; currentPos = ex.pos;
|
||
document.getElementById('custom-input').value = `head=[${ex.values.join(',')}], pos=${ex.pos}`;
|
||
// Update button states
|
||
document.querySelectorAll('.example-btn').forEach((b, i) => b.classList.toggle('active', i === idx));
|
||
startViz();
|
||
}
|
||
|
||
function loadCustom() {
|
||
const str = document.getElementById('custom-input').value.trim();
|
||
const parsed = parseInput(str);
|
||
if (!parsed) { alert('输入格式有误，请使用 head=[3,2,0,-4], pos=1'); return; }
|
||
currentValues = parsed.values; currentPos = parsed.pos;
|
||
document.querySelectorAll('.example-btn').forEach(b => b.classList.remove('active'));
|
||
startViz();
|
||
}
|
||
|
||
function startViz() {
|
||
sc.pause();
|
||
const steps = generateSteps(currentValues, currentPos);
|
||
sc.setSteps(steps);
|
||
renderCurrent(0, steps[0]);
|
||
}
|
||
|
||
function renderCurrent(idx, step) {
|
||
render(currentValues, currentPos, step);
|
||
updatePipeline(step.pipelineStage);
|
||
updateHint(step);
|
||
updateDetail(step);
|
||
updateResult(step);
|
||
updateCodeHighlight(step);
|
||
updateStepCounter(idx, sc.total());
|
||
updateControls(idx, sc.total(), sc.playing);
|
||
}
|
||
|
||
sc.onStep = renderCurrent;
|
||
sc.onPlay = function(playing) {
|
||
updateControls(sc.idx, sc.total(), playing);
|
||
};
|
||
|
||
/* ── Event Listeners ── */
|
||
document.querySelectorAll('.example-btn').forEach(btn => {
|
||
btn.addEventListener('click', () => loadExample(parseInt(btn.dataset.idx)));
|
||
});
|
||
|
||
document.getElementById('run-btn').addEventListener('click', loadCustom);
|
||
document.getElementById('custom-input').addEventListener('keydown', e => {
|
||
if (e.key === 'Enter') loadCustom();
|
||
});
|
||
|
||
document.getElementById('btn-first').addEventListener('click', () => sc.first());
|
||
document.getElementById('btn-prev').addEventListener('click', () => sc.prev());
|
||
document.getElementById('btn-play').addEventListener('click', () => sc.toggle());
|
||
document.getElementById('btn-next').addEventListener('click', () => sc.next());
|
||
document.getElementById('btn-last').addEventListener('click', () => sc.last());
|
||
|
||
// Keyboard shortcuts
|
||
document.addEventListener('keydown', e => {
|
||
if (e.target.tagName === 'INPUT') return;
|
||
if (e.key === 'ArrowLeft') { e.preventDefault(); sc.prev(); }
|
||
if (e.key === 'ArrowRight') { e.preventDefault(); sc.next(); }
|
||
if (e.key === ' ') { e.preventDefault(); sc.toggle(); }
|
||
});
|
||
|
||
/* ── Init ── */
|
||
loadExample(0);
|
||
|
||
})();
|
||
</script>
|
||
</body>
|
||
</html> |