583 lines
22 KiB
HTML
583 lines
22 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>022. 相交链表 – 图解</title>
|
|||
|
|
<link rel="stylesheet" href="../shared/style.css">
|
|||
|
|
<style>
|
|||
|
|
.vis-area{min-height:200px;padding:16px 0}
|
|||
|
|
.code-section{margin-top:16px}
|
|||
|
|
|
|||
|
|
/* ---- Y-shape layout ---- */
|
|||
|
|
.y-list{display:inline-flex;flex-direction:column;padding:8px 0;gap:0}
|
|||
|
|
.y-row{display:flex;align-items:center;gap:0;flex-wrap:nowrap;min-height:54px}
|
|||
|
|
.y-head{font-size:13px;font-weight:700;min-width:60px;text-align:right;margin-right:6px;white-space:nowrap;flex-shrink:0}
|
|||
|
|
.y-head.ha{color:var(--blue)}
|
|||
|
|
.y-head.hb{color:var(--orange)}
|
|||
|
|
.y-spacer{flex-shrink:0}
|
|||
|
|
.y-conn{font-size:22px;color:var(--purple);font-weight:700;flex-shrink:0;margin:0 4px;line-height:1}
|
|||
|
|
|
|||
|
|
/* Node wrapper for pointer labels */
|
|||
|
|
.nw{position:relative;display:inline-flex;flex-direction:column;align-items:center;flex-shrink:0}
|
|||
|
|
.nw .ptr{display:flex;flex-direction:column;align-items:center;font-size:10px;font-weight:700;margin-top:2px;line-height:1.2;gap:1px}
|
|||
|
|
.nw .ptr-pa{color:var(--blue)}
|
|||
|
|
.nw .ptr-pb{color:var(--orange)}
|
|||
|
|
.nw .ptr-ph{height:14px}
|
|||
|
|
|
|||
|
|
/* Shared / intersection highlight */
|
|||
|
|
.ll-node.is-intersect{border-color:var(--purple);box-shadow:0 0 0 3px rgba(139,92,246,.22)}
|
|||
|
|
.ll-node.is-intersect .val{background:#ede9fe;color:var(--purple-dark)}
|
|||
|
|
.ll-node.is-shared{border-color:#a78bfa}
|
|||
|
|
.ll-node.is-shared .val{background:#f5f3ff;color:#6d28d9}
|
|||
|
|
.ll-node.is-meet{border-color:var(--green)!important;box-shadow:0 0 0 4px rgba(22,163,74,.25)!important}
|
|||
|
|
.ll-node.is-meet .val{background:#dcfce7!important;color:var(--green-dark)!important}
|
|||
|
|
|
|||
|
|
/* null indicator in Y-list */
|
|||
|
|
.null-terminal{display:inline-flex;align-items:center;flex-shrink:0}
|
|||
|
|
|
|||
|
|
/* ---- Walk tracker ---- */
|
|||
|
|
.walk-wrap{margin-top:18px;padding:12px;background:#f8fafc;border-radius:12px;border:1px solid var(--border);overflow-x:auto}
|
|||
|
|
.walk-title{font-size:13px;font-weight:600;color:var(--text-secondary);margin-bottom:8px}
|
|||
|
|
.walk-row{display:flex;align-items:center;gap:0;margin:6px 0;flex-wrap:nowrap}
|
|||
|
|
.walk-tag{font-size:12px;font-weight:700;min-width:26px;margin-right:6px;flex-shrink:0}
|
|||
|
|
.walk-tag.wta{color:var(--blue)}
|
|||
|
|
.walk-tag.wtb{color:var(--orange)}
|
|||
|
|
.wc{
|
|||
|
|
display:inline-flex;align-items:center;justify-content:center;
|
|||
|
|
min-width:30px;height:26px;padding:1px 5px;border-radius:6px;
|
|||
|
|
font-size:11px;font-weight:600;font-family:monospace;transition:all .2s;
|
|||
|
|
background:#e2e8f0;color:var(--text);margin:0 1px;
|
|||
|
|
}
|
|||
|
|
.wc.wc-null{background:#f1f5f9;color:var(--text-muted);font-style:italic}
|
|||
|
|
.wc.wc-sh{border-bottom:2px solid var(--purple)}
|
|||
|
|
.wc.wc-sw{border-top:2px dashed #94a3b8}
|
|||
|
|
.wc.wc-a{box-shadow:0 0 0 2px var(--blue);background:#dbeafe;color:var(--blue-dark)}
|
|||
|
|
.wc.wc-b{box-shadow:0 0 0 2px var(--orange);background:#ffedd5;color:#9a3412}
|
|||
|
|
.wc.wc-meet{box-shadow:0 0 0 2px var(--green);background:#bbf7d0;color:var(--green-dark);font-weight:800}
|
|||
|
|
.ws{font-size:9px;color:var(--purple);font-weight:700;margin:0 2px}
|
|||
|
|
|
|||
|
|
/* ---- Info chips ---- */
|
|||
|
|
.info-row{display:flex;gap:10px;flex-wrap:wrap;margin:10px 0 4px;font-size:13px}
|
|||
|
|
.ic{padding:3px 10px;border-radius:999px;font-weight:600;font-size:12px}
|
|||
|
|
.ic-a{background:#dbeafe;color:var(--blue-dark)}
|
|||
|
|
.ic-b{background:#ffedd5;color:#9a3412}
|
|||
|
|
.ic-s{background:#ede9fe;color:var(--purple-dark)}
|
|||
|
|
.ic-g{background:#dcfce7;color:var(--green-dark)}
|
|||
|
|
</style>
|
|||
|
|
</head>
|
|||
|
|
<body>
|
|||
|
|
<div class="container">
|
|||
|
|
<h1>🟢 022. 相交链表 <span class="badge easy">简单</span></h1>
|
|||
|
|
<p class="subtitle">分类：链表 ｜ LeetCode 160 · Hot 100 #022</p>
|
|||
|
|
|
|||
|
|
<div class="controls" id="controls">
|
|||
|
|
<label for="inputArea">输入：</label>
|
|||
|
|
<input type="text" id="inputArea" placeholder="listA=[4,1,8,4,5], listB=[5,6,1,8,4,5], intersect=8">
|
|||
|
|
<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(){
|
|||
|
|
|
|||
|
|
/* ================================================================
|
|||
|
|
LeetCode 160 · 相交链表 · 双指针可视化
|
|||
|
|
算法：pA 走 listA 再走 listB，pB 走 listB 再走 listA，
|
|||
|
|
两者总步数相同 (m+n+2)，必在交点或 null 相遇。
|
|||
|
|
================================================================ */
|
|||
|
|
|
|||
|
|
var PIPE = ['init→初始化','step→步进','null→抵达末尾','switch→切换链表','meet→相遇'];
|
|||
|
|
|
|||
|
|
var examples = [
|
|||
|
|
{la:[4,1,8,4,5], lb:[5,6,1,8,4,5], iv:8, lbl:'示例1: intersect=8'},
|
|||
|
|
{la:[1,9,1,2,4], lb:[3,2,4], iv:2, lbl:'示例2: intersect=2'},
|
|||
|
|
{la:[2,6,4], lb:[1,5], iv:null, lbl:'示例3: 不相交'}
|
|||
|
|
];
|
|||
|
|
|
|||
|
|
var gLA, gLB, gSA, gSB, gHI;
|
|||
|
|
var steps, ctrl;
|
|||
|
|
|
|||
|
|
// ────────── parse & compute ──────────
|
|||
|
|
|
|||
|
|
function parseInput(s){
|
|||
|
|
var a=s.match(/listA=\[([^\]]*)\]/), b=s.match(/listB=\[([^\]]*)\]/), v=s.match(/intersect=(\S+)/);
|
|||
|
|
if(!a||!b) return null;
|
|||
|
|
return {
|
|||
|
|
la: a[1]?a[1].split(',').map(Number):[],
|
|||
|
|
lb: b[1]?b[1].split(',').map(Number):[],
|
|||
|
|
iv: v?(v[1]==='null'||v[1]==='0'?null:Number(v[1])):null
|
|||
|
|
};
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function calcSkips(la,lb,iv){
|
|||
|
|
if(iv==null) return {sa:la.length,sb:lb.length,hi:false};
|
|||
|
|
var sa=-1;
|
|||
|
|
for(var i=0;i<la.length;i++) if(la[i]===iv){sa=i;break;}
|
|||
|
|
if(sa===-1) return {sa:la.length,sb:lb.length,hi:false};
|
|||
|
|
var tail=la.slice(sa), sb=-1;
|
|||
|
|
for(var s=0;s<=lb.length-tail.length;s++){
|
|||
|
|
var ok=true;
|
|||
|
|
for(var j=0;j<tail.length;j++) if(lb[s+j]!==tail[j]){ok=false;break;}
|
|||
|
|
if(ok){sb=s;break;}
|
|||
|
|
}
|
|||
|
|
if(sb===-1) return {sa:la.length,sb:lb.length,hi:false};
|
|||
|
|
return {sa:sa,sb:sb,hi:true};
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function nid(list,idx,skip,pfx){
|
|||
|
|
if(idx>=list.length) return 'null';
|
|||
|
|
if(gHI && idx>=skip) return 's'+(idx-skip);
|
|||
|
|
return pfx+idx;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ────────── build walk sequences ──────────
|
|||
|
|
|
|||
|
|
function mkWalk(list,len,skip,pfx,otherList,otherLen,otherSkip,otherPfx){
|
|||
|
|
var arr=[];
|
|||
|
|
for(var i=0;i<len;i++)
|
|||
|
|
arr.push({L:list===gLA?'A':'B',i:i,n:nid(list,i,skip,pfx),v:list[i],nu:false,sw:false});
|
|||
|
|
arr.push({L:list===gLA?'A':'B',i:len,n:'null',v:null,nu:true,sw:false});
|
|||
|
|
var swAt=arr.length-1;
|
|||
|
|
var oL=otherList===gLA?'A':'B';
|
|||
|
|
for(var i=0;i<otherLen;i++)
|
|||
|
|
arr.push({L:oL,i:i,n:nid(otherList,i,otherSkip,otherPfx),v:otherList[i],nu:false,sw:true});
|
|||
|
|
arr.push({L:oL,i:otherLen,n:'null2',v:null,nu:true,sw:true});
|
|||
|
|
return {arr:arr,swAt:swAt};
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ────────── step generation ──────────
|
|||
|
|
|
|||
|
|
function buildSteps(){
|
|||
|
|
steps=[];
|
|||
|
|
var la=gLA,lb=gLB,sA=gSA,sB=gSB,hi=gHI;
|
|||
|
|
var wA=mkWalk(la,la.length,sA,'a', lb,lb.length,sB,'b');
|
|||
|
|
var wB=mkWalk(lb,lb.length,sB,'b', la,la.length,sA,'a');
|
|||
|
|
|
|||
|
|
// Step 0: init
|
|||
|
|
var a0=wA.arr[0],b0=wB.arr[0];
|
|||
|
|
steps.push({
|
|||
|
|
stg:'init', wi:0, pa:a0, pb:b0,
|
|||
|
|
msg:'初始化：pA = headA → node '+a0.n+'(val='+a0.v+')，pB = headB → node '+b0.n+'(val='+b0.v+')',
|
|||
|
|
cl:4
|
|||
|
|
});
|
|||
|
|
if(a0.n===b0.n){steps[0].stg='meet';steps[0].msg='两指针从同一节点出发 → 直接相遇';return steps;}
|
|||
|
|
|
|||
|
|
var maxW=Math.max(wA.arr.length,wB.arr.length);
|
|||
|
|
for(var w=1;w<maxW;w++){
|
|||
|
|
if(w>=wA.arr.length||w>=wB.arr.length) break;
|
|||
|
|
var a=wA.arr[w], b=wB.arr[w];
|
|||
|
|
var pa=wA.arr[w-1], pb=wB.arr[w-1];
|
|||
|
|
var met=(a.n===b.n);
|
|||
|
|
var aRn=a.nu&&!pa.nu; // pA just reached null
|
|||
|
|
var bRn=b.nu&&!pb.nu;
|
|||
|
|
var aSw=a.sw&&!pa.sw; // pA just switched lists
|
|||
|
|
var bSw=b.sw&&!pb.sw;
|
|||
|
|
|
|||
|
|
var stg,msg,cl;
|
|||
|
|
|
|||
|
|
if(met){
|
|||
|
|
stg='meet'; cl=7;
|
|||
|
|
msg=a.nu
|
|||
|
|
?'pA 和 pB 都到达 null → 两链表不相交，返回 null'
|
|||
|
|
:'pA 和 pB 在 node '+a.n+'(val='+a.v+') 相遇 → 找到交点！';
|
|||
|
|
} else if(aRn&&bRn){
|
|||
|
|
stg='null'; cl=5;
|
|||
|
|
msg='pA 抵达 listA 末尾(null)，pB 抵达 listB 末尾(null)';
|
|||
|
|
} else if(aRn&&bSw){
|
|||
|
|
stg='null'; cl=5;
|
|||
|
|
msg='pA 抵达 '+a.L+' 末尾(null)，pB 从 null 切换到 head'+
|
|||
|
|
(b.L==='A'?'A':'B')+'(node '+b.n+', val='+b.v+')';
|
|||
|
|
} else if(bRn&&aSw){
|
|||
|
|
stg='null'; cl=6;
|
|||
|
|
msg='pB 抵达 '+b.L+' 末尾(null)，pA 从 null 切换到 head'+
|
|||
|
|
(a.L==='B'?'B':'A')+'(node '+a.n+', val='+a.v+')';
|
|||
|
|
} else if(aRn){
|
|||
|
|
stg='null'; cl=5;
|
|||
|
|
msg='pA 抵达 '+pa.L+' 末尾(null)，pB 在 '+b.L+'['+b.i+']=node '+b.n+'(val='+b.v+')';
|
|||
|
|
} else if(bRn){
|
|||
|
|
stg='null'; cl=6;
|
|||
|
|
msg='pB 抵达 '+pb.L+' 末尾(null)，pA 在 '+a.L+'['+a.i+']=node '+a.n+'(val='+a.v+')';
|
|||
|
|
} else if(aSw&&bSw){
|
|||
|
|
stg='switch'; cl=5;
|
|||
|
|
msg='pA 切换到 headB(node '+a.n+', val='+a.v+')，pB 切换到 headA(node '+b.n+', val='+b.v+')';
|
|||
|
|
} else if(aSw){
|
|||
|
|
stg='switch'; cl=5;
|
|||
|
|
msg='pA 从 null 切换到 headB(node '+a.n+', val='+a.v+')，pB 走到 '+b.L+'['+b.i+']=node '+b.n+'(val='+b.v+')';
|
|||
|
|
} else if(bSw){
|
|||
|
|
stg='switch'; cl=6;
|
|||
|
|
msg='pB 从 null 切换到 headA(node '+b.n+', val='+b.v+')，pA 走到 '+a.L+'['+a.i+']=node '+a.n+'(val='+a.v+')';
|
|||
|
|
} else {
|
|||
|
|
stg='step'; cl=5;
|
|||
|
|
msg='pA: '+a.L+'['+a.i+']='+a.v+' (node '+a.n+')，pB: '+b.L+'['+b.i+']='+b.v+' (node '+b.n+')，pA ≠ pB';
|
|||
|
|
}
|
|||
|
|
steps.push({stg:stg,wi:w,pa:a,pb:b,met:met,msg:msg,cl:cl});
|
|||
|
|
if(stg==='meet') break;
|
|||
|
|
}
|
|||
|
|
return steps;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ────────── render: node helper ──────────
|
|||
|
|
|
|||
|
|
function rNode(val, cls, ptrs, arrowOverride){
|
|||
|
|
var html='<div class="nw">';
|
|||
|
|
html+='<div class="ll-node '+cls+'"><span class="val">'+val+'</span>';
|
|||
|
|
html+='<span class="arrow">'+(arrowOverride||'→')+'</span></div>';
|
|||
|
|
if(ptrs&&ptrs.length){
|
|||
|
|
html+='<div class="ptr">';
|
|||
|
|
for(var p=0;p<ptrs.length;p++){
|
|||
|
|
html+=ptrs[p]==='pA'
|
|||
|
|
?'<span class="ptr-pa">▼pA</span>'
|
|||
|
|
:'<span class="ptr-pb">▼pB</span>';
|
|||
|
|
}
|
|||
|
|
html+='</div>';
|
|||
|
|
} else {
|
|||
|
|
html+='<div class="ptr-ph"></div>';
|
|||
|
|
}
|
|||
|
|
html+='</div>';
|
|||
|
|
return html;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ────────── render: Y-shape linked list ──────────
|
|||
|
|
|
|||
|
|
function renderYList(pa,pb){
|
|||
|
|
var la=gLA,lb=gLB,sA=gSA,sB=gSB,hi=gHI;
|
|||
|
|
var aExcl=la.slice(0,sA), bExcl=lb.slice(0,sB), shared=hi?la.slice(sA):[];
|
|||
|
|
|
|||
|
|
if(!hi){
|
|||
|
|
// ── No intersection: two complete rows ──
|
|||
|
|
return renderTwoRows(la,lb,pa,pb);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ── Y-shape: three segments ──
|
|||
|
|
var unitPx=104, headPx=66;
|
|||
|
|
var aBW=headPx+aExcl.length*unitPx;
|
|||
|
|
var bBW=headPx+bExcl.length*unitPx;
|
|||
|
|
var maxBW=Math.max(aBW,bBW);
|
|||
|
|
var sharedML=maxBW+10;
|
|||
|
|
var aPad=Math.max(0,bBW-aBW);
|
|||
|
|
var bPad=Math.max(0,aBW-bBW);
|
|||
|
|
|
|||
|
|
var h='<div class="y-list">';
|
|||
|
|
|
|||
|
|
// ── Branch A ──
|
|||
|
|
h+='<div class="y-row">';
|
|||
|
|
h+='<span class="y-head ha">headA →</span>';
|
|||
|
|
for(var i=0;i<aExcl.length;i++){
|
|||
|
|
var nd='a'+i;
|
|||
|
|
var isPA=pa&&!pa.nu&&pa.L==='A'&&pa.i===i;
|
|||
|
|
var isPB=pb&&!pb.nu&&pb.L==='A'&&pb.i===i&&pb.n===nd;
|
|||
|
|
var ptrs=[]; if(isPA) ptrs.push('pA'); if(isPB) ptrs.push('pB');
|
|||
|
|
h+=rNode(aExcl[i],isPA||isPB?'current':'',ptrs);
|
|||
|
|
}
|
|||
|
|
if(aPad>0) h+='<span class="y-spacer" style="width:'+aPad+'px"></span>';
|
|||
|
|
h+='<span class="y-conn">↘</span>';
|
|||
|
|
h+='</div>';
|
|||
|
|
|
|||
|
|
// ── Shared row ──
|
|||
|
|
h+='<div class="y-row" style="margin-left:'+sharedML+'px">';
|
|||
|
|
for(var i=0;i<shared.length;i++){
|
|||
|
|
var nd='s'+i;
|
|||
|
|
var isPA=pa&&!pa.nu&&pa.n===nd;
|
|||
|
|
var isPB=pb&&!pb.nu&&pb.n===nd;
|
|||
|
|
var cls=i===0?'is-intersect':'is-shared';
|
|||
|
|
if(isPA&&isPB) cls+=' is-meet';
|
|||
|
|
else if(isPA||isPB) cls+=' current';
|
|||
|
|
var ptrs=[]; if(isPA) ptrs.push('pA'); if(isPB) ptrs.push('pB');
|
|||
|
|
var isLast=i===shared.length-1;
|
|||
|
|
h+=rNode(shared[i],cls,ptrs,isLast?'∅':'→');
|
|||
|
|
}
|
|||
|
|
if(shared.length===0){
|
|||
|
|
h+='<div class="nw"><div class="ll-node null-node"><span class="val">∅</span></div><div class="ptr-ph"></div></div>';
|
|||
|
|
}
|
|||
|
|
h+='</div>';
|
|||
|
|
|
|||
|
|
// ── Branch B ──
|
|||
|
|
h+='<div class="y-row">';
|
|||
|
|
h+='<span class="y-head hb">headB →</span>';
|
|||
|
|
for(var i=0;i<bExcl.length;i++){
|
|||
|
|
var nd='b'+i;
|
|||
|
|
var isPA=pa&&!pa.nu&&pa.L==='B'&&pa.i===i&&pa.n===nd;
|
|||
|
|
var isPB=pb&&!pb.nu&&pb.L==='B'&&pb.i===i&&pb.n===nd;
|
|||
|
|
var ptrs=[]; if(isPA) ptrs.push('pA'); if(isPB) ptrs.push('pB');
|
|||
|
|
h+=rNode(bExcl[i],isPA||isPB?'current':'',ptrs);
|
|||
|
|
}
|
|||
|
|
if(bPad>0) h+='<span class="y-spacer" style="width:'+bPad+'px"></span>';
|
|||
|
|
h+='<span class="y-conn">↗</span>';
|
|||
|
|
h+='</div>';
|
|||
|
|
|
|||
|
|
h+='</div>';
|
|||
|
|
return h;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ── No intersection: two full rows ──
|
|||
|
|
function renderTwoRows(la,lb,pa,pb){
|
|||
|
|
var h='<div class="y-list">';
|
|||
|
|
// ListA
|
|||
|
|
h+='<div class="y-row">';
|
|||
|
|
h+='<span class="y-head ha">headA →</span>';
|
|||
|
|
for(var i=0;i<la.length;i++){
|
|||
|
|
var isPA=pa&&!pa.nu&&pa.L==='A'&&pa.i===i;
|
|||
|
|
var isPB=pb&&!pb.nu&&pb.L==='A'&&pb.i===i;
|
|||
|
|
var ptrs=[]; if(isPA) ptrs.push('pA'); if(isPB) ptrs.push('pB');
|
|||
|
|
h+=rNode(la[i],isPA||isPB?'current':'',ptrs,i===la.length-1?'∅':'→');
|
|||
|
|
}
|
|||
|
|
h+='</div>';
|
|||
|
|
// ListB
|
|||
|
|
h+='<div class="y-row" style="margin-top:12px">';
|
|||
|
|
h+='<span class="y-head hb">headB →</span>';
|
|||
|
|
for(var i=0;i<lb.length;i++){
|
|||
|
|
var isPA=pa&&!pa.nu&&pa.L==='B'&&pa.i===i;
|
|||
|
|
var isPB=pb&&!pb.nu&&pb.L==='B'&&pb.i===i;
|
|||
|
|
var ptrs=[]; if(isPA) ptrs.push('pA'); if(isPB) ptrs.push('pB');
|
|||
|
|
h+=rNode(lb[i],isPA||isPB?'current':'',ptrs,i===lb.length-1?'∅':'→');
|
|||
|
|
}
|
|||
|
|
h+='</div>';
|
|||
|
|
h+='</div>';
|
|||
|
|
return h;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ────────── render: walk path tracker ──────────
|
|||
|
|
|
|||
|
|
function renderWalk(pa,pb,wi){
|
|||
|
|
var la=gLA,lb=gLB,sA=gSA,sB=gSB,hi=gHI;
|
|||
|
|
|
|||
|
|
var wADat=mkWalk(la,la.length,sA,'a', lb,lb.length,sB,'b');
|
|||
|
|
var wBDat=mkWalk(lb,lb.length,sB,'b', la,la.length,sA,'a');
|
|||
|
|
var wA=wADat.arr, wB=wBDat.arr;
|
|||
|
|
var swA=wADat.swAt, swB=wBDat.swAt;
|
|||
|
|
|
|||
|
|
function chip(c,i,tag){
|
|||
|
|
var cls='wc';
|
|||
|
|
if(c.nu) cls+=' wc-null';
|
|||
|
|
if(!c.nu&&c.sh()) cls+=' wc-sh';
|
|||
|
|
if(c.sw) cls+=' wc-sw';
|
|||
|
|
if(i===wi){
|
|||
|
|
var bothMet=pa&&pb&&pa.n===pb.n&&!pa.nu;
|
|||
|
|
if(tag==='pA') cls+=bothMet?' wc-meet':' wc-a';
|
|||
|
|
else cls+=bothMet?' wc-meet':' wc-b';
|
|||
|
|
}
|
|||
|
|
return '<span class="'+cls+'" title="node '+c.n+'">'+c.v+'</span>';
|
|||
|
|
}
|
|||
|
|
// add .sh() method to walk items
|
|||
|
|
wA.forEach(function(x){ x.sh=function(){return hi&&x.n.charAt(0)==='s';}; });
|
|||
|
|
wB.forEach(function(x){ x.sh=function(){return hi&&x.n.charAt(0)==='s';}; });
|
|||
|
|
|
|||
|
|
function row(arr,swAt,tag){
|
|||
|
|
var h='<div class="walk-row"><span class="walk-tag '+(tag==='pA'?'wta':'wtb')+'">'+tag+'</span>';
|
|||
|
|
for(var i=0;i<arr.length;i++){
|
|||
|
|
if(i===swAt+1) h+='<span class="ws">│</span>';
|
|||
|
|
h+=chip(arr[i],i,tag);
|
|||
|
|
}
|
|||
|
|
h+='</div>';
|
|||
|
|
return h;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
var h='<div class="walk-wrap">';
|
|||
|
|
h+='<div class="walk-title">🚶 指针行走路径 <span style="margin-left:10px;font-size:11px;color:var(--text-muted)">│=切换链表分界 紫色下划线=共享节点</span></div>';
|
|||
|
|
h+=row(wA,swA,'pA');
|
|||
|
|
h+=row(wB,swB,'pB');
|
|||
|
|
|
|||
|
|
// Step counter
|
|||
|
|
if(wi>0){
|
|||
|
|
var totalA=la.length+1+lb.length+1, totalB=lb.length+1+la.length+1;
|
|||
|
|
h+='<div style="margin-top:4px;font-size:11px;color:var(--text-secondary)">';
|
|||
|
|
h+='pA 已走 '+Math.min(wi+1,totalA)+' / '+totalA+' 步';
|
|||
|
|
h+=' · ';
|
|||
|
|
var paOnB=wi>la.length;
|
|||
|
|
var pbOnA=wi>lb.length;
|
|||
|
|
if(paOnB) h+='<span style="color:var(--orange)">pA 在 listB 上</span>';
|
|||
|
|
else h+='pA 在 listA 上';
|
|||
|
|
h+=' · ';
|
|||
|
|
if(pbOnA) h+='<span style="color:var(--blue)">pB 在 listA 上</span>';
|
|||
|
|
else h+='pB 在 listB 上';
|
|||
|
|
h+='</div>';
|
|||
|
|
}
|
|||
|
|
h+='</div>';
|
|||
|
|
return h;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ────────── render: info chips ──────────
|
|||
|
|
|
|||
|
|
function renderInfo(pa,pb){
|
|||
|
|
var h='<div class="info-row">';
|
|||
|
|
if(pa){
|
|||
|
|
if(pa.nu) h+='<span class="ic ic-a">pA = null</span>';
|
|||
|
|
else h+='<span class="ic ic-a">pA → '+pa.L+'['+pa.i+'] = node '+pa.n+'</span>';
|
|||
|
|
}
|
|||
|
|
if(pb){
|
|||
|
|
if(pb.nu) h+='<span class="ic ic-b">pB = null</span>';
|
|||
|
|
else h+='<span class="ic ic-b">pB → '+pb.L+'['+pb.i+'] = node '+pb.n+'</span>';
|
|||
|
|
}
|
|||
|
|
if(pa&&pb&&!pa.nu&&!pb.nu&&pa.n===pb.n) h+='<span class="ic ic-g">pA == pB ✓</span>';
|
|||
|
|
if(pa&&pb&&pa.nu&&pb.nu) h+='<span class="ic ic-g">pA == pB (null) ✓</span>';
|
|||
|
|
h+='</div>';
|
|||
|
|
return h;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ────────── pipeline ──────────
|
|||
|
|
|
|||
|
|
function setPipeline(cur){
|
|||
|
|
$('pipeline').innerHTML=PIPE.map(function(s){
|
|||
|
|
var p=s.split('→');
|
|||
|
|
return '<span class="pipe-step '+(cur===p[0]?'active':'')+'">'+p[1]+'</span>';
|
|||
|
|
}).join('<i>→</i>');
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ────────── main render ──────────
|
|||
|
|
|
|||
|
|
function render(idx){
|
|||
|
|
if(!steps||!steps[idx]) return;
|
|||
|
|
var s=steps[idx];
|
|||
|
|
|
|||
|
|
// Viz area
|
|||
|
|
var viz=renderYList(s.pa,s.pb);
|
|||
|
|
viz+=renderWalk(s.pa,s.pb,s.wi||0);
|
|||
|
|
viz+=renderInfo(s.pa,s.pb);
|
|||
|
|
$('vizArea').innerHTML=viz;
|
|||
|
|
|
|||
|
|
// Detail panel
|
|||
|
|
var d='<div class="calc-block">'+s.msg+'</div>';
|
|||
|
|
d+='<div style="margin-top:8px">';
|
|||
|
|
d+=s.pa.nu?'<code>pA = null</code>':'<code>pA → '+s.pa.L+'['+s.pa.i+'] = node '+s.pa.n+'</code>';
|
|||
|
|
d+=' ';
|
|||
|
|
d+=s.pb.nu?'<code>pB = null</code>':'<code>pB → '+s.pb.L+'['+s.pb.i+'] = node '+s.pb.n+'</code>';
|
|||
|
|
d+='</div>';
|
|||
|
|
if(!s.pa.nu&&!s.pb.nu){
|
|||
|
|
d+='<div style="margin-top:6px;font-size:13px">';
|
|||
|
|
if(s.pa.n===s.pb.n)
|
|||
|
|
d+='<span style="color:var(--green);font-weight:700">pA.nodeId === pB.nodeId → 指向同一内存节点！</span>';
|
|||
|
|
else
|
|||
|
|
d+='<span style="color:var(--red)">pA.nodeId ('+s.pa.n+') ≠ pB.nodeId ('+s.pb.n+') → 不同节点</span>';
|
|||
|
|
d+='</div>';
|
|||
|
|
}
|
|||
|
|
if(s.stg==='step')
|
|||
|
|
d+='<div style="margin-top:8px;font-size:12px;color:var(--text-secondary)">while pA ≠ pB → 继续前进：pA = pA.next, pB = pB.next</div>';
|
|||
|
|
else if(s.stg==='null')
|
|||
|
|
d+='<div style="margin-top:8px;font-size:12px;color:var(--text-secondary)">指针到达链表末尾 → 下一步将切换到另一链表头部 (pA→headB / pB→headA)</div>';
|
|||
|
|
else if(s.stg==='switch')
|
|||
|
|
d+='<div style="margin-top:8px;font-size:12px;color:var(--text-secondary)">走完一条链表后切换，保证两指针走的总步数相同 (lenA+lenB)</div>';
|
|||
|
|
$('detailContent').innerHTML=d;
|
|||
|
|
|
|||
|
|
// Result panel
|
|||
|
|
if(s.stg==='meet'){
|
|||
|
|
if(s.pa.nu){
|
|||
|
|
$('resultContent').innerHTML='<div class="final-answer" style="border-color:#f87171;background:#fef2f2">两链表不相交，返回 <b>null</b><br><span style="font-size:13px;color:#64748b">pA 和 pB 各走 lenA+lenB 步后在 null 处相遇</span><br><div class="complexity">时间 O(m+n) · 空间 O(1)</div></div>';
|
|||
|
|
} else {
|
|||
|
|
$('resultContent').innerHTML='<div class="final-answer">交点节点：<b>node '+s.pa.n+' (val='+s.pa.v+')</b><br><span style="font-size:13px;color:#64748b">经过 '+s.wi+' 步迭代后 pA == pB → 找到交点</span><br><div class="complexity">时间 O(m+n) · 空间 O(1)</div></div>';
|
|||
|
|
}
|
|||
|
|
} else {
|
|||
|
|
$('resultContent').innerHTML='等待完成…';
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// Hint & counters
|
|||
|
|
$('hintText').textContent=s.msg;
|
|||
|
|
$('stepInfo').textContent='步骤 '+(idx+1)+' / '+steps.length;
|
|||
|
|
setPipeline(s.stg);
|
|||
|
|
|
|||
|
|
// Code highlight
|
|||
|
|
$('codeArea').innerHTML=renderCode(PY,{highlightLines:s.cl?[s.cl]:[],lang:'Python'});
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ────────── Python code ──────────
|
|||
|
|
|
|||
|
|
var PY=[
|
|||
|
|
'class Solution:',
|
|||
|
|
' def getIntersectionNode(self, headA, headB):',
|
|||
|
|
' if not headA or not headB:',
|
|||
|
|
' return None',
|
|||
|
|
' pA, pB = headA, headB',
|
|||
|
|
' while pA != pB:',
|
|||
|
|
' pA = pA.next if pA else headB',
|
|||
|
|
' pB = pB.next if pB else headA',
|
|||
|
|
' return pA'
|
|||
|
|
].join('\n');
|
|||
|
|
|
|||
|
|
// ────────── init ──────────
|
|||
|
|
|
|||
|
|
function loadExample(idx){
|
|||
|
|
var e=examples[idx];
|
|||
|
|
gLA=e.la.slice(); gLB=e.lb.slice();
|
|||
|
|
var sk=calcSkips(gLA,gLB,e.iv);
|
|||
|
|
gSA=sk.sa; gSB=sk.sb; gHI=sk.hi;
|
|||
|
|
$('inputArea').value='listA=['+gLA.join(',')+'], listB=['+gLB.join(',')+'], intersect='+(e.iv===null?'null':e.iv);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function init(){
|
|||
|
|
var sel=$('exampleSelect');
|
|||
|
|
examples.forEach(function(e,i){ sel.innerHTML+='<option value="'+i+'">'+e.lbl+'</option>'; });
|
|||
|
|
|
|||
|
|
loadExample(0);
|
|||
|
|
buildSteps();
|
|||
|
|
|
|||
|
|
ctrl=new StepController({onStep:render,autoInterval:700});
|
|||
|
|
ctrl.setSteps(steps.map(function(_,i){return i;}));
|
|||
|
|
|
|||
|
|
$('applyBtn').onclick=function(){
|
|||
|
|
var p=parseInput($('inputArea').value);
|
|||
|
|
if(!p){alert('格式: listA=[4,1,8,4,5], listB=[5,6,1,8,4,5], intersect=8');return;}
|
|||
|
|
gLA=p.la; gLB=p.lb;
|
|||
|
|
var sk=calcSkips(gLA,gLB,p.iv); gSA=sk.sa; gSB=sk.sb; gHI=sk.hi;
|
|||
|
|
buildSteps(); ctrl.setSteps(steps.map(function(_,i){return i;})); render(0);
|
|||
|
|
};
|
|||
|
|
$('exampleSelect').onchange=function(){
|
|||
|
|
loadExample(parseInt($('exampleSelect').value));
|
|||
|
|
buildSteps(); ctrl.setSteps(steps.map(function(_,i){return i;})); render(0);
|
|||
|
|
$('autoBtn').textContent='自动播放';
|
|||
|
|
};
|
|||
|
|
$('prevBtn').onclick=function(){ctrl.prev();};
|
|||
|
|
$('nextBtn').onclick=function(){ctrl.next();};
|
|||
|
|
$('jumpBtn').onclick=function(){ctrl.jumpToEnd();};
|
|||
|
|
$('autoBtn').onclick=function(){var on=ctrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
|||
|
|
$('resetBtn').onclick=function(){ctrl.reset();$('autoBtn').textContent='自动播放';};
|
|||
|
|
|
|||
|
|
render(0);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
init();
|
|||
|
|
|
|||
|
|
})();
|
|||
|
|
</script>
|
|||
|
|
</body>
|
|||
|
|
</html>
|