852 lines
33 KiB
HTML
852 lines
33 KiB
HTML
<!DOCTYPE html>
|
||
<html lang="zh-Hans">
|
||
<head>
|
||
<meta charset="UTF-8">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
||
<title>030. 两两交换链表中的节点 – 图解</title>
|
||
<link rel="stylesheet" href="../shared/style.css">
|
||
<style>
|
||
.vis-area { min-height: 200px; padding: 16px 0; }
|
||
.code-section { margin-top: 16px; }
|
||
|
||
/* ---- SVG Linked List ---- */
|
||
.ll-svg-wrap { overflow-x: auto; padding: 8px 0; }
|
||
.ll-svg-wrap svg { display: block; min-width: 400px; }
|
||
|
||
/* ---- Swap Focus Diagram ---- */
|
||
.swap-focus {
|
||
margin-top: 20px; padding: 16px; background: #f8fafc;
|
||
border: 2px solid #e2e8f0; border-radius: 12px; overflow-x: auto;
|
||
}
|
||
.swap-focus .op-badge {
|
||
display: inline-block; padding: 4px 12px; border-radius: 999px;
|
||
font-size: 13px; font-weight: 700; margin-bottom: 12px;
|
||
}
|
||
.swap-focus .op-badge.remove {
|
||
background: #fee2e2; color: #991b1b; border: 1px solid #fca5a5;
|
||
}
|
||
.swap-focus .op-badge.add {
|
||
background: #dcfce7; color: #166534; border: 1px solid #86efac;
|
||
}
|
||
.swap-focus svg { display: block; margin-top: 8px; }
|
||
|
||
/* ---- Legend ---- */
|
||
.legend-row {
|
||
display: flex; flex-wrap: wrap; gap: 14px; margin: 10px 0 4px; font-size: 12px; color: var(--text-secondary);
|
||
}
|
||
.legend-row span { display: inline-flex; align-items: center; gap: 4px; }
|
||
.legend-dot {
|
||
width: 14px; height: 3px; border-radius: 2px; display: inline-block;
|
||
}
|
||
.legend-dot.normal { background: var(--blue); }
|
||
.legend-dot.removed { background: var(--red); border-top: 2px dashed var(--red); height: 0; }
|
||
.legend-dot.added { background: var(--green); height: 4px; }
|
||
|
||
/* ---- Pointer key ---- */
|
||
.ptr-key {
|
||
display: flex; flex-wrap: wrap; gap: 10px; margin: 8px 0; font-size: 12px;
|
||
}
|
||
.ptr-key span { display: inline-flex; align-items: center; gap: 3px; }
|
||
.ptr-dot {
|
||
width: 10px; height: 10px; border-radius: 3px; display: inline-block;
|
||
}
|
||
.ptr-dot.c-prev { background: #166534; }
|
||
.ptr-dot.c-first { background: #92400e; }
|
||
.ptr-dot.c-second { background: #5b21b6; }
|
||
.ptr-dot.c-temp { background: #155e75; }
|
||
</style>
|
||
</head>
|
||
<body>
|
||
<div class="container">
|
||
<h1>🟡 030. 两两交换链表中的节点 <span class="badge medium">中等</span></h1>
|
||
<p class="subtitle">分类：链表 ｜ LeetCode Hot 100</p>
|
||
|
||
<!-- 控制面板 -->
|
||
<div class="controls" id="controls">
|
||
<label for="inputArea">输入：</label>
|
||
<input type="text" id="inputArea" value="head=[1,2,3,4]" placeholder="head=[1,2,3,4]">
|
||
<button id="applyBtn" class="primary">生成图解</button>
|
||
<select id="exampleSelect"></select>
|
||
<span style="flex:1"></span>
|
||
<button id="prevBtn">◀ 上一步</button>
|
||
<button id="nextBtn">下一步 ▶</button>
|
||
<button id="jumpBtn">⏭ 跳到结果</button>
|
||
<button id="autoBtn">自动播放</button>
|
||
<button id="resetBtn">重置</button>
|
||
</div>
|
||
|
||
<!-- 步骤流水线 -->
|
||
<div class="pipeline" id="pipeline"></div>
|
||
|
||
<!-- 提示条 -->
|
||
<div class="hint info" id="hintBox">
|
||
<span id="stepInfo"></span><br>
|
||
<span id="hintText">点击「生成图解」开始</span>
|
||
</div>
|
||
|
||
<!-- 可视化面板 -->
|
||
<div class="panels">
|
||
<div class="panel" id="mainPanel">
|
||
<h3>📊 可视化 — 链表结构与指针变化</h3>
|
||
<div class="vis-area" id="vizArea">点击「生成图解」开始</div>
|
||
</div>
|
||
<div class="panel-grid">
|
||
<div class="panel" id="detailPanel">
|
||
<h3>📝 当前步骤详情</h3>
|
||
<div id="detailContent">等待开始...</div>
|
||
</div>
|
||
<div class="panel" id="resultPanel">
|
||
<h3>✅ 结果</h3>
|
||
<div id="resultContent">等待完成...</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
|
||
<!-- 代码 -->
|
||
<div class="panel code-section">
|
||
<h3>💻 参考代码（Python）</h3>
|
||
<div id="codeArea"></div>
|
||
</div>
|
||
|
||
<footer>Powered by QwenPaw · 图解算法 · LeetCode Hot 100</footer>
|
||
</div>
|
||
|
||
<script src="../shared/algo-viz.js"></script>
|
||
<script>
|
||
"use strict";
|
||
(function() {
|
||
// ========== Constants ==========
|
||
const PIPELINE_STAGES = ['初始化', '识别节点对', '三步交换', '前进', '完成'];
|
||
const CODE = `class Solution:
|
||
def swapPairs(self, head):
|
||
dummy = ListNode(0, head)
|
||
prev = dummy
|
||
while prev.next and prev.next.next:
|
||
first = prev.next
|
||
second = prev.next.next
|
||
first.next = second.next
|
||
second.next = first
|
||
prev.next = second
|
||
prev = first
|
||
return dummy.next`;
|
||
|
||
const examples = [
|
||
{ input: [1,2,3,4], label: '示例1: [1,2,3,4] → [2,1,4,3]' },
|
||
{ input: [], label: '示例2: [] → []' },
|
||
{ input: [1], label: '示例3: [1] → [1]' },
|
||
{ input: [1,2,3], label: '示例4: [1,2,3] → [2,1,3]' },
|
||
{ input: [1,2], label: '示例5: [1,2] → [2,1]' },
|
||
];
|
||
|
||
// ========== State ==========
|
||
let steps = [], stepCtrl;
|
||
|
||
// ========== Linked List Simulation ==========
|
||
// Nodes: index 0 = dummy(val='D'), 1..n = value nodes, nullId = n+1
|
||
function simulate(values) {
|
||
const nullId = values.length + 1;
|
||
const nodes = []; // { id, val, next }
|
||
const nextMap = {}; // id → nextId
|
||
|
||
// Build initial list
|
||
nodes.push({ id: 0, val: 'D', next: values.length > 0 ? 1 : nullId });
|
||
nextMap[0] = values.length > 0 ? 1 : nullId;
|
||
for (let i = 0; i < values.length; i++) {
|
||
const id = i + 1;
|
||
nodes.push({ id, val: values[i], next: id + 1 });
|
||
nextMap[id] = id + 1;
|
||
}
|
||
|
||
function snapshot() { return Object.assign({}, nextMap); }
|
||
function traversal() {
|
||
const order = [];
|
||
let cur = nextMap[0];
|
||
while (cur !== nullId) { order.push(cur); cur = nextMap[cur]; }
|
||
return order;
|
||
}
|
||
function valOf(id) { return id === nullId ? 'NULL' : id === 0 ? 'D' : nodes[id].val; }
|
||
|
||
const stepsArr = [];
|
||
|
||
// ---- Step: Initialize ----
|
||
stepsArr.push({
|
||
stage: '初始化',
|
||
msg: '创建虚拟头节点 dummy，令 prev = dummy',
|
||
detail: 'dummy 指向链表头部，prev 从 dummy 开始遍历\n虚拟头节点简化了头节点交换时的边界处理，无需特殊判断',
|
||
nextMap: snapshot(),
|
||
ptrs: { prev: 0 },
|
||
highlights: { 0: 'prev' },
|
||
arrowOps: [],
|
||
codeLines: [3, 4],
|
||
swapFocus: null,
|
||
});
|
||
|
||
let prevId = 0;
|
||
|
||
while (true) {
|
||
const firstId = nextMap[prevId];
|
||
const secondId = firstId !== nullId ? nextMap[firstId] : nullId;
|
||
|
||
// Check: need two nodes to swap
|
||
if (firstId === nullId || secondId === nullId) {
|
||
const reason = firstId === nullId
|
||
? `prev.next 为 NULL，不足两个节点`
|
||
: `prev.next.next 为 NULL，只剩一个节点 ${valOf(firstId)}，无需交换`;
|
||
stepsArr.push({
|
||
stage: '完成',
|
||
msg: `循环条件不满足：${reason}`,
|
||
detail: `while 条件: prev.next and prev.next.next\n${reason}\n循环结束，返回 dummy.next`,
|
||
nextMap: snapshot(),
|
||
ptrs: { prev: prevId },
|
||
highlights: {},
|
||
arrowOps: [],
|
||
codeLines: [5, 12],
|
||
swapFocus: null,
|
||
});
|
||
break;
|
||
}
|
||
|
||
const tempId = nextMap[secondId];
|
||
|
||
// ---- Step: Identify pair ----
|
||
stepsArr.push({
|
||
stage: '识别节点对',
|
||
msg: `识别节点对：first=${valOf(firstId)}, second=${valOf(secondId)}, 保存 temp=${valOf(tempId)}`,
|
||
detail: `prev.next = ${valOf(firstId)} ≠ NULL ✓\nprev.next.next = ${valOf(secondId)} ≠ NULL ✓\n可以交换！\n\nfirst = prev.next = ${valOf(firstId)}\nsecond = prev.next.next = ${valOf(secondId)}\ntemp = second.next = ${valOf(tempId)}`,
|
||
nextMap: snapshot(),
|
||
ptrs: { prev: prevId, first: firstId, second: secondId, temp: tempId },
|
||
highlights: { [prevId]: 'prev', [firstId]: 'first', [secondId]: 'second', [tempId]: 'temp' },
|
||
arrowOps: [],
|
||
codeLines: [5, 6, 7],
|
||
swapFocus: null,
|
||
});
|
||
|
||
// ---- Swap Step 1: first.next = second.next ----
|
||
const oldFirstNext = nextMap[firstId];
|
||
nextMap[firstId] = tempId;
|
||
stepsArr.push({
|
||
stage: '三步交换',
|
||
msg: `第一步：first.next = second.next → ${valOf(firstId)}.next = ${valOf(tempId)}`,
|
||
detail: `断开 first(${valOf(firstId)}) → second(${valOf(secondId)}) 的连接\n建立 first(${valOf(firstId)}) → temp(${valOf(tempId)}) 的新连接\n\n保存了 second.next 后，first 不再指向 second\n这样 second 才能安全地指向 first`,
|
||
nextMap: snapshot(),
|
||
ptrs: { prev: prevId, first: firstId, second: secondId, temp: tempId },
|
||
highlights: { [prevId]: 'prev', [firstId]: 'first', [secondId]: 'second', [tempId]: 'temp' },
|
||
arrowOps: [
|
||
{ from: firstId, to: oldFirstNext, type: 'remove' },
|
||
{ from: firstId, to: tempId, type: 'add' },
|
||
],
|
||
codeLines: [8],
|
||
swapFocus: { op: `first.next = second.next`, prevId, firstId, secondId, tempId,
|
||
removed: [{ from: firstId, to: secondId }],
|
||
added: [{ from: firstId, to: tempId }],
|
||
},
|
||
});
|
||
|
||
// ---- Swap Step 2: second.next = first ----
|
||
const oldSecondNext = nextMap[secondId];
|
||
nextMap[secondId] = firstId;
|
||
stepsArr.push({
|
||
stage: '三步交换',
|
||
msg: `第二步：second.next = first → ${valOf(secondId)}.next = ${valOf(firstId)}`,
|
||
detail: `断开 second(${valOf(secondId)}) → temp(${valOf(tempId)}) 的连接\n建立 second(${valOf(secondId)}) → first(${valOf(firstId)}) 的新连接\n\n这是交换的核心：second 反过来指向 first\n完成这一步后，second→first 链已形成`,
|
||
nextMap: snapshot(),
|
||
ptrs: { prev: prevId, first: firstId, second: secondId, temp: tempId },
|
||
highlights: { [prevId]: 'prev', [firstId]: 'first', [secondId]: 'second', [tempId]: 'temp' },
|
||
arrowOps: [
|
||
{ from: secondId, to: oldSecondNext, type: 'remove' },
|
||
{ from: secondId, to: firstId, type: 'add' },
|
||
],
|
||
codeLines: [9],
|
||
swapFocus: { op: `second.next = first`, prevId, firstId, secondId, tempId,
|
||
removed: [{ from: secondId, to: tempId }],
|
||
added: [{ from: secondId, to: firstId }],
|
||
},
|
||
});
|
||
|
||
// ---- Swap Step 3: prev.next = second ----
|
||
const oldPrevNext = nextMap[prevId];
|
||
nextMap[prevId] = secondId;
|
||
stepsArr.push({
|
||
stage: '三步交换',
|
||
msg: `第三步：prev.next = second → ${valOf(prevId)}.next = ${valOf(secondId)}`,
|
||
detail: `断开 prev(${valOf(prevId)}) → first(${valOf(firstId)}) 的连接\n建立 prev(${valOf(prevId)}) → second(${valOf(secondId)}) 的新连接\n\n这一步将交换后的子链重新接入主链\n交换完成！新顺序：${valOf(prevId)} → ${valOf(secondId)} → ${valOf(firstId)} → ${valOf(tempId)}`,
|
||
nextMap: snapshot(),
|
||
ptrs: { prev: prevId, first: firstId, second: secondId, temp: tempId },
|
||
highlights: { [prevId]: 'prev', [firstId]: 'first', [secondId]: 'second', [tempId]: 'temp' },
|
||
arrowOps: [
|
||
{ from: prevId, to: oldPrevNext, type: 'remove' },
|
||
{ from: prevId, to: secondId, type: 'add' },
|
||
],
|
||
codeLines: [10],
|
||
swapFocus: { op: `prev.next = second`, prevId, firstId, secondId, tempId,
|
||
removed: [{ from: prevId, to: firstId }],
|
||
added: [{ from: prevId, to: secondId }],
|
||
},
|
||
});
|
||
|
||
// ---- Advance: prev = first ----
|
||
prevId = firstId;
|
||
nextMap[prevId]; // just to reference
|
||
stepsArr.push({
|
||
stage: '前进',
|
||
msg: `前进：prev = first = ${valOf(firstId)}`,
|
||
detail: `prev 移动到已交换好的前一个位置 (= first)\n此时 prev 后面的两个节点将是下一对要交换的\n\n当前链表：${(() => {
|
||
const t = traversal(); return 'D → ' + t.map(id => valOf(id)).join(' → ') + ' → NULL';
|
||
})()}`,
|
||
nextMap: snapshot(),
|
||
ptrs: { prev: prevId },
|
||
highlights: { [prevId]: 'prev' },
|
||
arrowOps: [],
|
||
codeLines: [11],
|
||
swapFocus: null,
|
||
});
|
||
}
|
||
|
||
// ---- Final Result ----
|
||
const result = traversal();
|
||
const resultStr = result.length > 0 ? result.map(id => valOf(id)).join(' → ') + ' → NULL' : 'NULL (空链表)';
|
||
// Only add if the last step wasn't already the "完成" stage
|
||
const lastStep = stepsArr[stepsArr.length - 1];
|
||
if (lastStep.stage !== '完成' || !lastStep.isFinal) {
|
||
stepsArr.push({
|
||
stage: '完成',
|
||
msg: `返回 dummy.next，交换完成！`,
|
||
detail: `最终结果：${resultStr}\n\n每个相邻节点对都已两两交换\n虚拟头节点 dummy 的作用：\n • 统一头节点的处理逻辑\n • 避免 prev 为 None 的边界判断`,
|
||
nextMap: snapshot(),
|
||
ptrs: {},
|
||
highlights: {},
|
||
arrowOps: [],
|
||
codeLines: [12],
|
||
swapFocus: null,
|
||
isFinal: true,
|
||
result: result.map(id => valOf(id)),
|
||
});
|
||
}
|
||
|
||
return { stepsArr, nodes, nullId };
|
||
}
|
||
|
||
// ========== Rendering ==========
|
||
|
||
// --- Pipeline ---
|
||
function renderPipeline(activeStage) {
|
||
let html = '';
|
||
PIPELINE_STAGES.forEach((s, i) => {
|
||
if (i > 0) html += '<i>→</i>';
|
||
html += `<span class="pipe-step${s === activeStage ? ' active' : ''}">${s}</span>`;
|
||
});
|
||
$('pipeline').innerHTML = html;
|
||
}
|
||
|
||
// --- Main SVG Linked List ---
|
||
function renderListSVG(nextMap, nodes, nullId, ptrs, highlights, arrowOps) {
|
||
const nodeW = 68, nodeH = 40, gapX = 40, startY = 56;
|
||
const maxPerRow = 6;
|
||
const rowGap = 80;
|
||
const labelH = 36;
|
||
|
||
// Determine all node IDs to draw (always include dummy + all value nodes + null)
|
||
const allIds = [0];
|
||
for (let i = 1; i < nullId; i++) allIds.push(i);
|
||
allIds.push(nullId);
|
||
|
||
// Calculate positions
|
||
const posMap = {};
|
||
let x = 10, y = startY;
|
||
allIds.forEach((id, idx) => {
|
||
if (idx > 0 && idx % maxPerRow === 0) { x = 10; y += rowGap + labelH; }
|
||
posMap[id] = { x, y };
|
||
x += nodeW + gapX;
|
||
});
|
||
|
||
const svgW = Math.max(420, x + 10);
|
||
const svgH = y + nodeH + labelH + 20;
|
||
|
||
const arrowMarkerDefs = `
|
||
<defs>
|
||
<marker id="ah-normal" markerWidth="8" markerHeight="6" refX="7" refY="3" orient="auto">
|
||
<path d="M0,0 L8,3 L0,6 Z" fill="#3b82f6"/>
|
||
</marker>
|
||
<marker id="ah-added" markerWidth="10" markerHeight="8" refX="9" refY="4" orient="auto">
|
||
<path d="M0,0 L10,4 L0,8 Z" fill="#16a34a"/>
|
||
</marker>
|
||
<marker id="ah-removed" markerWidth="8" markerHeight="6" refX="7" refY="3" orient="auto">
|
||
<path d="M0,0 L8,3 L0,6 Z" fill="#ef4444" opacity="0.5"/>
|
||
</marker>
|
||
<marker id="ah-null" markerWidth="6" markerHeight="6" refX="5" refY="3" orient="auto">
|
||
<path d="M0,0 L6,3 L0,6 Z" fill="#94a3b8"/>
|
||
</marker>
|
||
</defs>`;
|
||
|
||
let svg = `<svg width="100%" viewBox="0 0 ${svgW} ${svgH}" xmlns="http://www.w3.org/2000/svg" style="font-family:inherit;">`;
|
||
svg += arrowMarkerDefs;
|
||
|
||
// --- Draw arrows layer (behind nodes) ---
|
||
// Collect arrow operations for quick lookup
|
||
const removeSet = new Set();
|
||
const addSet = new Set();
|
||
if (arrowOps) {
|
||
arrowOps.forEach(op => {
|
||
const key = op.from + '->' + op.to;
|
||
if (op.type === 'remove') removeSet.add(key);
|
||
if (op.type === 'add') addSet.add(key);
|
||
});
|
||
}
|
||
|
||
// Draw normal arrows from nextMap (skip ones being removed)
|
||
const drawnKeys = new Set();
|
||
Object.entries(nextMap).forEach(([fromStr, toId]) => {
|
||
const fromId = parseInt(fromStr);
|
||
// Only draw from non-null nodes (and skip nodes past the end)
|
||
if (fromId > nullId || fromId === nullId) return;
|
||
const key = fromId + '->' + toId;
|
||
|
||
// Skip if this arrow is being removed (we'll draw it differently)
|
||
if (removeSet.has(key)) return;
|
||
|
||
// Skip if this is going to be drawn as "added"
|
||
// (We draw added arrows on top later)
|
||
if (addSet.has(key)) return;
|
||
|
||
const fromPos = posMap[fromId];
|
||
if (!fromPos) return;
|
||
|
||
if (toId === nullId) {
|
||
// Arrow to NULL
|
||
const nullPos = posMap[nullId];
|
||
if (nullPos) {
|
||
svg += drawArrowPath(fromPos, nullPos, nodeW, nodeH, 'null');
|
||
}
|
||
} else {
|
||
const toPos = posMap[toId];
|
||
if (toPos) {
|
||
drawnKeys.add(key);
|
||
svg += drawArrowPath(fromPos, toPos, nodeW, nodeH, 'normal');
|
||
}
|
||
}
|
||
});
|
||
|
||
// Draw removed arrows (red dashed)
|
||
if (arrowOps) {
|
||
arrowOps.filter(op => op.type === 'remove').forEach(op => {
|
||
const fromPos = posMap[op.from];
|
||
const toPos = posMap[op.to];
|
||
if (fromPos && toPos) {
|
||
svg += drawArrowPath(fromPos, toPos, nodeW, nodeH, 'removed');
|
||
}
|
||
});
|
||
}
|
||
|
||
// Draw added arrows (green bold)
|
||
if (arrowOps) {
|
||
arrowOps.filter(op => op.type === 'add').forEach(op => {
|
||
const fromPos = posMap[op.from];
|
||
const toPos = posMap[op.to];
|
||
if (fromPos && toPos) {
|
||
svg += drawArrowPath(fromPos, toPos, nodeW, nodeH, 'added');
|
||
}
|
||
});
|
||
}
|
||
|
||
// --- Draw nodes ---
|
||
allIds.forEach(id => {
|
||
const p = posMap[id];
|
||
const hl = highlights[id] || '';
|
||
const isNull = id === nullId;
|
||
const isDummy = id === 0;
|
||
const val = isNull ? 'NULL' : isDummy ? 'D' : nodes[id].val;
|
||
|
||
// Node rect
|
||
let fill, stroke, textFill, rx = 8;
|
||
if (isNull) {
|
||
fill = '#f1f5f9'; stroke = '#94a3b8'; textFill = '#94a3b8';
|
||
rx = 4;
|
||
} else if (hl === 'prev') {
|
||
fill = '#dcfce7'; stroke = '#16a34a'; textFill = '#166534';
|
||
} else if (hl === 'first') {
|
||
fill = '#fef3c7'; stroke = '#f59e0b'; textFill = '#92400e';
|
||
} else if (hl === 'second') {
|
||
fill = '#ede9fe'; stroke = '#8b5cf6'; textFill = '#5b21b6';
|
||
} else if (hl === 'temp') {
|
||
fill = '#cffafe'; stroke = '#06b6d4'; textFill = '#155e75';
|
||
} else if (isDummy) {
|
||
fill = '#f1f5f9'; stroke = '#64748b'; textFill = '#475569';
|
||
} else {
|
||
fill = '#dbeafe'; stroke = '#3b82f6'; textFill = '#1e40af';
|
||
}
|
||
|
||
if (isNull) {
|
||
svg += `<rect x="${p.x}" y="${p.y}" width="${nodeW - 20}" height="${nodeH}" rx="${rx}" fill="${fill}" stroke="${stroke}" stroke-width="1.5" stroke-dasharray="5,3"/>`;
|
||
svg += `<text x="${p.x + (nodeW - 20)/2}" y="${p.y + nodeH/2 + 5}" text-anchor="middle" fill="${textFill}" font-size="12" font-weight="600" font-style="italic">${val}</text>`;
|
||
} else {
|
||
svg += `<rect x="${p.x}" y="${p.y}" width="${nodeW}" height="${nodeH}" rx="${rx}" fill="${fill}" stroke="${stroke}" stroke-width="2"/>`;
|
||
svg += `<text x="${p.x + nodeW/2}" y="${p.y + nodeH/2 + 5}" text-anchor="middle" fill="${textFill}" font-size="15" font-weight="700">${val}</text>`;
|
||
|
||
// Draw the "next" cell separator
|
||
svg += `<line x1="${p.x + nodeW - 22}" y1="${p.y}" x2="${p.x + nodeW - 22}" y2="${p.y + nodeH}" stroke="${stroke}" stroke-width="1" opacity="0.3"/>`;
|
||
svg += `<text x="${p.x + nodeW - 11}" y="${p.y + nodeH/2 + 4}" text-anchor="middle" fill="${stroke}" font-size="13" opacity="0.5">•</text>`;
|
||
|
||
// Highlight glow
|
||
if (hl === 'prev' || hl === 'first' || hl === 'second' || hl === 'temp') {
|
||
svg += `<rect x="${p.x - 3}" y="${p.y - 3}" width="${nodeW + 6}" height="${nodeH + 6}" rx="${rx + 2}" fill="none" stroke="${stroke}" stroke-width="1.5" opacity="0.25"/>`;
|
||
}
|
||
}
|
||
});
|
||
|
||
// --- Draw pointer labels below nodes ---
|
||
const ptrEntries = Object.entries(ptrs);
|
||
if (ptrEntries.length > 0) {
|
||
allIds.forEach(id => {
|
||
const p = posMap[id];
|
||
if (!p) return;
|
||
const labels = ptrEntries.filter(([_, nodeId]) => nodeId === id).map(([name]) => name);
|
||
if (labels.length === 0) return;
|
||
|
||
const isNull = id === nullId;
|
||
const cx = isNull ? p.x + (nodeW - 20)/2 : p.x + nodeW/2;
|
||
const cy = p.y + nodeH + 14;
|
||
|
||
labels.forEach((label, li) => {
|
||
let color;
|
||
switch(label) {
|
||
case 'prev': color = '#16a34a'; break;
|
||
case 'first': color = '#f59e0b'; break;
|
||
case 'second': color = '#8b5cf6'; break;
|
||
case 'temp': color = '#06b6d4'; break;
|
||
default: color = '#64748b';
|
||
}
|
||
// Small triangle pointer
|
||
svg += `<polygon points="${cx},${cy - 10} ${cx - 5},${cy - 15} ${cx + 5},${cy - 15}" fill="${color}"/>`;
|
||
svg += `<text x="${cx}" y="${cy + li * 14}" text-anchor="middle" fill="${color}" font-size="11" font-weight="700">${label}</text>`;
|
||
});
|
||
});
|
||
}
|
||
|
||
svg += '</svg>';
|
||
return svg;
|
||
}
|
||
|
||
// Draw an SVG arrow path between two node positions
|
||
function drawArrowPath(fromPos, toPos, nodeW, nodeH, style, nullIdOpt) {
|
||
// Arrow start: right center of source node (source is never null)
|
||
const x1 = fromPos.x + nodeW;
|
||
const y1 = fromPos.y + nodeH / 2;
|
||
|
||
// Arrow end: left center of target node
|
||
const x2 = toPos.x;
|
||
const y2 = toPos.y + nodeH / 2;
|
||
|
||
// Determine if we need a curve
|
||
// Same row: forward arrow
|
||
// Different row: curve down/up
|
||
// Backward: curve above
|
||
const sameRow = Math.abs(y1 - y2) < 5;
|
||
const forward = x2 > x1 + 10;
|
||
let pathD;
|
||
|
||
if (sameRow && forward) {
|
||
// Straight arrow
|
||
pathD = `M ${x1} ${y1} L ${x2} ${y2}`;
|
||
} else if (sameRow && !forward) {
|
||
// Backward arrow on same row — curve above
|
||
const midX = (x1 + x2) / 2;
|
||
const curveH = Math.max(30, Math.abs(x2 - x1) * 0.4);
|
||
pathD = `M ${x1} ${y1} Q ${midX} ${y1 - curveH} ${x2} ${y2}`;
|
||
} else {
|
||
// Different row — curve
|
||
const midX = (x1 + x2) / 2;
|
||
const midY = (y1 + y2) / 2 - 20;
|
||
pathD = `M ${x1} ${y1} Q ${midX} ${midY} ${x2} ${y2}`;
|
||
}
|
||
|
||
let strokeColor, strokeWidth, dashArray, opacity, markerId;
|
||
switch(style) {
|
||
case 'normal':
|
||
strokeColor = '#3b82f6'; strokeWidth = 2; dashArray = ''; opacity = 0.85; markerId = 'ah-normal'; break;
|
||
case 'removed':
|
||
strokeColor = '#ef4444'; strokeWidth = 2; dashArray = '6,4'; opacity = 0.5; markerId = 'ah-removed'; break;
|
||
case 'added':
|
||
strokeColor = '#16a34a'; strokeWidth = 3; dashArray = ''; opacity = 1; markerId = 'ah-added'; break;
|
||
case 'null':
|
||
strokeColor = '#94a3b8'; strokeWidth = 1.5; dashArray = '4,3'; opacity = 0.6; markerId = 'ah-null'; break;
|
||
default:
|
||
strokeColor = '#94a3b8'; strokeWidth = 1.5; dashArray = ''; opacity = 0.5; markerId = 'ah-normal';
|
||
}
|
||
|
||
return `<path d="${pathD}" fill="none" stroke="${strokeColor}" stroke-width="${strokeWidth}" stroke-dasharray="${dashArray}" opacity="${opacity}" marker-end="url(#${markerId})"/>`;
|
||
}
|
||
|
||
// --- Swap Focus Diagram ---
|
||
function renderSwapFocus(focus, nodes, nullId) {
|
||
if (!focus) return '';
|
||
|
||
const { op, prevId, firstId, secondId, tempId, removed, added } = focus;
|
||
function v(id) { return id === nullId ? 'NULL' : id === 0 ? 'D' : nodes[id].val; }
|
||
function label(id) {
|
||
if (id === prevId) return 'prev';
|
||
if (id === firstId) return 'first';
|
||
if (id === secondId) return 'second';
|
||
if (id === tempId) return 'temp';
|
||
return '';
|
||
}
|
||
|
||
const nodeW = 64, nodeH = 38, gapX = 56;
|
||
const startY = 44;
|
||
const ids = [prevId, firstId, secondId, tempId];
|
||
const positions = {};
|
||
ids.forEach((id, i) => { positions[id] = { x: 16 + i * (nodeW + gapX), y: startY }; });
|
||
|
||
const svgW = 16 + ids.length * (nodeW + gapX) - gapX + 16;
|
||
const svgH = startY + nodeH + 50;
|
||
|
||
const defs = `
|
||
<defs>
|
||
<marker id="sf-ah-normal" markerWidth="8" markerHeight="6" refX="7" refY="3" orient="auto">
|
||
<path d="M0,0 L8,3 L0,6 Z" fill="#94a3b8"/>
|
||
</marker>
|
||
<marker id="sf-ah-removed" markerWidth="8" markerHeight="6" refX="7" refY="3" orient="auto">
|
||
<path d="M0,0 L8,3 L0,6 Z" fill="#ef4444" opacity="0.6"/>
|
||
</marker>
|
||
<marker id="sf-ah-added" markerWidth="10" markerHeight="8" refX="9" refY="4" orient="auto">
|
||
<path d="M0,0 L10,4 L0,8 Z" fill="#16a34a"/>
|
||
</marker>
|
||
</defs>`;
|
||
|
||
let svg = `<svg width="100%" viewBox="0 0 ${svgW} ${svgH}" xmlns="http://www.w3.org/2000/svg" style="font-family:inherit;">`;
|
||
svg += defs;
|
||
|
||
// Draw unchanged arrows (gray, between adjacent nodes from left to right)
|
||
const removedFromSet = new Set(removed.map(r => r.from));
|
||
const addedFromSet = new Set(added.map(a => a.from));
|
||
|
||
for (let i = 0; i < ids.length - 1; i++) {
|
||
const fromId = ids[i], toId = ids[i + 1];
|
||
const isRemoved = removed.some(r => r.from === fromId && r.to === toId);
|
||
const isAdded = added.some(a => a.from === fromId && a.to === toId);
|
||
|
||
if (!isRemoved && !isAdded) {
|
||
// Unchanged connection
|
||
const fp = positions[fromId], tp = positions[toId];
|
||
const x1 = fp.x + nodeW, y1 = fp.y + nodeH / 2;
|
||
const x2 = tp.x, y2 = tp.y + nodeH / 2;
|
||
svg += `<line x1="${x1}" y1="${y1}" x2="${x2}" y2="${y2}" stroke="#94a3b8" stroke-width="2" marker-end="url(#sf-ah-normal)"/>`;
|
||
}
|
||
}
|
||
|
||
// Draw removed arrows
|
||
removed.forEach(r => {
|
||
const fp = positions[r.from], tp = positions[r.to];
|
||
if (!fp || !tp) return;
|
||
const x1 = fp.x + nodeW, y1 = fp.y + nodeH / 2;
|
||
const x2 = tp.x, y2 = tp.y + nodeH / 2;
|
||
// For backward or non-adjacent arrows, use a curve
|
||
if (x2 <= x1 + 10) {
|
||
const midX = (x1 + x2) / 2;
|
||
svg += `<path d="M ${x1} ${y1} Q ${midX} ${y1 - 28} ${x2} ${y2}" fill="none" stroke="#ef4444" stroke-width="2" stroke-dasharray="6,4" opacity="0.5" marker-end="url(#sf-ah-removed)"/>`;
|
||
} else {
|
||
svg += `<line x1="${x1}" y1="${y1}" x2="${x2}" y2="${y2}" stroke="#ef4444" stroke-width="2" stroke-dasharray="6,4" opacity="0.5" marker-end="url(#sf-ah-removed)"/>`;
|
||
}
|
||
// X mark on the removed arrow
|
||
const midX = (x1 + x2) / 2, midY = (y1 + y2) / 2;
|
||
svg += `<text x="${midX}" y="${midY - 8}" text-anchor="middle" fill="#ef4444" font-size="14" font-weight="800">✕</text>`;
|
||
});
|
||
|
||
// Draw added arrows
|
||
added.forEach(a => {
|
||
const fp = positions[a.from], tp = positions[a.to];
|
||
if (!fp || !tp) return;
|
||
const x1 = fp.x + nodeW, y1 = fp.y + nodeH / 2;
|
||
const x2 = tp.x, y2 = tp.y + nodeH / 2;
|
||
|
||
// Determine offset to not overlap with removed arrow
|
||
let yOffset = 0;
|
||
const isRemovedSameDirection = removed.some(r => r.from === a.from);
|
||
if (isRemovedSameDirection) yOffset = -14; // curve above to show new arrow
|
||
|
||
if (x2 <= x1 + 10 || yOffset !== 0) {
|
||
// Curved arrow (backward or offset from removed)
|
||
const midX = (x1 + x2) / 2;
|
||
const curveOffset = Math.max(28, Math.abs(x1 - x2) * 0.3) + Math.abs(yOffset);
|
||
svg += `<path d="M ${x1} ${y1} Q ${midX} ${y1 - curveOffset} ${x2} ${y2}" fill="none" stroke="#16a34a" stroke-width="3" marker-end="url(#sf-ah-added)"/>`;
|
||
} else {
|
||
svg += `<line x1="${x1}" y1="${y1}" x2="${x2}" y2="${y2}" stroke="#16a34a" stroke-width="3" marker-end="url(#sf-ah-added)"/>`;
|
||
}
|
||
});
|
||
|
||
// Draw nodes
|
||
ids.forEach(id => {
|
||
const p = positions[id];
|
||
const isNull = id === nullId;
|
||
const isDummyNode = id === 0;
|
||
const val = v(id);
|
||
|
||
let fill, stroke, textFill;
|
||
if (id === prevId) { fill = '#dcfce7'; stroke = '#16a34a'; textFill = '#166534'; }
|
||
else if (id === firstId) { fill = '#fef3c7'; stroke = '#f59e0b'; textFill = '#92400e'; }
|
||
else if (id === secondId) { fill = '#ede9fe'; stroke = '#8b5cf6'; textFill = '#5b21b6'; }
|
||
else if (id === tempId) { fill = '#cffafe'; stroke = '#06b6d4'; textFill = '#155e75'; }
|
||
else if (isNull) { fill = '#f1f5f9'; stroke = '#94a3b8'; textFill = '#94a3b8'; }
|
||
else if (isDummyNode){ fill = '#f1f5f9'; stroke = '#64748b'; textFill = '#475569'; }
|
||
else { fill = '#dbeafe'; stroke = '#3b82f6'; textFill = '#1e40af'; }
|
||
|
||
const w = isNull ? nodeW - 16 : nodeW;
|
||
svg += `<rect x="${p.x}" y="${p.y}" width="${w}" height="${nodeH}" rx="8" fill="${fill}" stroke="${stroke}" stroke-width="2"/>`;
|
||
svg += `<text x="${p.x + w/2}" y="${p.y + nodeH/2 + 5}" text-anchor="middle" fill="${textFill}" font-size="14" font-weight="700">${val}</text>`;
|
||
|
||
// Label below
|
||
const lb = label(id);
|
||
if (lb) {
|
||
svg += `<text x="${p.x + w/2}" y="${p.y + nodeH + 14}" text-anchor="middle" fill="${stroke}" font-size="11" font-weight="700">${lb}</text>`;
|
||
}
|
||
});
|
||
|
||
svg += '</svg>';
|
||
|
||
// Build full swap focus HTML
|
||
let html = '<div class="swap-focus">';
|
||
html += `<div style="font-size:14px;font-weight:700;margin-bottom:8px;">🔍 交换细节 — <code style="font-size:15px;">${op}</code></div>`;
|
||
|
||
// Badges
|
||
if (removed.length > 0) {
|
||
html += `<span class="op-badge remove">✕ 删除：${removed.map(r => `${v(r.from)}→${v(r.to)}`).join(', ')}</span> `;
|
||
}
|
||
if (added.length > 0) {
|
||
html += `<span class="op-badge add">✓ 新增：${added.map(a => `${v(a.from)}→${v(a.to)}`).join(', ')}</span>`;
|
||
}
|
||
|
||
html += '<div class="ll-svg-wrap">' + svg + '</div>';
|
||
|
||
// Legend
|
||
html += '<div class="legend-row">';
|
||
html += '<span><span class="legend-dot normal"></span> 未改变</span>';
|
||
html += '<span><span class="legend-dot removed"></span> 删除的连接</span>';
|
||
html += '<span><span class="legend-dot added"></span> 新增的连接</span>';
|
||
html += '</div>';
|
||
|
||
html += '</div>';
|
||
return html;
|
||
}
|
||
|
||
// --- Pointer key legend ---
|
||
function renderPtrKey() {
|
||
return '<div class="ptr-key">' +
|
||
'<span><span class="ptr-dot c-prev"></span> prev</span>' +
|
||
'<span><span class="ptr-dot c-first"></span> first</span>' +
|
||
'<span><span class="ptr-dot c-second"></span> second</span>' +
|
||
'<span><span class="ptr-dot c-temp"></span> temp</span>' +
|
||
'</div>';
|
||
}
|
||
|
||
// ========== Main Render ==========
|
||
let simNodes, simNullId;
|
||
|
||
function render(stepIdx) {
|
||
const s = steps[stepIdx];
|
||
renderPipeline(s.stage);
|
||
|
||
// Main visualization
|
||
let vizHtml = renderPtrKey();
|
||
vizHtml += '<div class="ll-svg-wrap">' + renderListSVG(s.nextMap, simNodes, simNullId, s.ptrs, s.highlights, s.arrowOps) + '</div>';
|
||
|
||
// Swap focus (only for swap sub-steps)
|
||
if (s.swapFocus) {
|
||
vizHtml += renderSwapFocus(s.swapFocus, simNodes, simNullId);
|
||
}
|
||
|
||
$('vizArea').innerHTML = vizHtml;
|
||
|
||
// Detail panel
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.detail.replace(/\n/g, '<br>') + '</div>';
|
||
|
||
// Result panel
|
||
if (s.isFinal && s.result) {
|
||
const resStr = s.result.length > 0 ? s.result.join(' → ') + ' → NULL' : 'NULL (空链表)';
|
||
$('resultContent').innerHTML = `<div class="final-answer">交换结果：<b>${resStr}</b><div class="complexity">时间复杂度 O(n) | 空间复杂度 O(1)</div></div>`;
|
||
} else if (s.stage === '完成' && !s.isFinal) {
|
||
// Intermediate "完成" step (loop exit, before final result)
|
||
// Don't overwrite result
|
||
}
|
||
|
||
// Hint
|
||
$('hintText').textContent = s.msg;
|
||
|
||
// Code highlight
|
||
$('codeArea').innerHTML = renderCode(CODE, { highlightLines: s.codeLines || [], lang: 'Python' });
|
||
}
|
||
|
||
// ========== Parse Input ==========
|
||
function parseInput() {
|
||
const raw = $('inputArea').value.trim();
|
||
const m = raw.match(/head\s*=\s*\[([^\]]*)\]/);
|
||
if (!m) {
|
||
alert('输入格式：head=[1,2,3,4]');
|
||
return null;
|
||
}
|
||
const inner = m[1].trim();
|
||
if (inner === '') return [];
|
||
return inner.split(',').map(s => parseInt(s.trim())).filter(n => !isNaN(n));
|
||
}
|
||
|
||
// ========== Build & Init ==========
|
||
function buildAndStart(values) {
|
||
const sim = simulate(values);
|
||
steps = sim.stepsArr;
|
||
simNodes = sim.nodes;
|
||
simNullId = sim.nullId;
|
||
|
||
stepCtrl = new StepController({
|
||
onStep: (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx + 1} / ${steps.length}`; },
|
||
onComplete: () => {},
|
||
autoInterval: 800,
|
||
});
|
||
stepCtrl.setSteps(steps.map((_, i) => i));
|
||
|
||
render(0);
|
||
$('stepInfo').textContent = `步骤 1 / ${steps.length}`;
|
||
$('autoBtn').textContent = '自动播放';
|
||
}
|
||
|
||
function init() {
|
||
// Populate examples
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e, i) => {
|
||
sel.innerHTML += `<option value="${i}">${e.label}</option>`;
|
||
});
|
||
|
||
// Default start
|
||
buildAndStart(examples[0].input);
|
||
|
||
// Event handlers
|
||
$('applyBtn').onclick = () => {
|
||
const values = parseInput();
|
||
if (values !== null) buildAndStart(values);
|
||
};
|
||
|
||
sel.onchange = () => {
|
||
const e = examples[parseInt(sel.value)];
|
||
$('inputArea').value = `head=[${e.input.join(',')}]`;
|
||
buildAndStart(e.input);
|
||
};
|
||
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => {
|
||
const on = stepCtrl.toggleAuto();
|
||
$('autoBtn').textContent = on ? '暂停' : '自动播放';
|
||
};
|
||
$('resetBtn').onclick = () => {
|
||
stepCtrl.reset();
|
||
$('autoBtn').textContent = '自动播放';
|
||
};
|
||
}
|
||
|
||
init();
|
||
|
||
// Render code initially
|
||
$('codeArea').innerHTML = renderCode(CODE, { lang: 'Python' });
|
||
})();
|
||
</script>
|
||
</body>
|
||
</html>
|