第一幕：算法朝会，秦使发难
一眼春秋，望穿风云。
第一章：链表分治，初露锋芒
第一幕：算法朝会，秦使发难
齐国，临淄城，算法殿。
晨光透过雕花木窗，在青石地面上投下斑驳光影。大殿中央，一丈见方的水镜悬浮空中，波纹流转——正是列国敬畏的“天机算法系统”。
齐威王端坐龙纹宝座，眉宇间隐现忧色。殿下文武分立两侧，左侧以宰相邹忌为首，右侧以上将军田忌为尊。
“诸位爱卿，”齐威王声音低沉，“天机系统已出今日之题。谁能解之，赏千金，封上卿！”
水镜波纹骤变，浮现金色篆文：
【王诏·链表分封令】
【场景】：秦王点兵改制，甲士营将士依序而列，各佩功勋数
【龙门线】：阈值 叁
【改制令】：功勋小于伍 者立左阵，大于等于伍者立右阵
【铁律】：左、右阵中，诸将士初始前后次序不可乱
【当前最佳解法】：秦相商鞅之’两度遍历册录法’】
“哈哈哈！”
一声长笑打破沉寂。黑袍秦使踏前一步，腰间玉佩叮当作响，正是秦国第一算法大师——商鞅。
“齐王陛下，”商鞅拱手，眼中却无半分敬意，“我大秦‘双重遍历法’，虽复杂度略高，但堂堂正正，势如破竹！不知齐国可有更高明解法？”
他袖袍一挥，水镜显现解法：
/**
**【题目：链表分区】**
**【描述】：给定单链表头结点 head 与整数 x，请分隔链表，使所有小于 x 的节点皆在大于等于 x 的节点之前**
**【约束】：须保持节点初始相对位置**
**【当前最佳】：时间复杂度 O(n²)，空间复杂度 O(n)，提供者——秦使商鞅】**
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
提示：
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200
*/
// 秦国解法：双重遍历法
public ListNode partition(ListNode head, int x) {
// 第一次遍历：收集所有小于x的节点
List<ListNode> smallList = new ArrayList<>();
ListNode p = head;
while (p != null) {
if (p.val < x) smallList.add(p);
p = p.next;
}
// 第二次遍历：收集所有大于等于x的节点
List<ListNode> largeList = new ArrayList<>();
p = head;
while (p != null) {
if (p.val >= x) largeList.add(p);
p = p.next;
}
// 拼接新链表
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
for (ListNode node : smallList) {
curr.next = node;
curr = curr.next;
}
for (ListNode node : largeList) {
curr.next = node;
curr = curr.next;
}
curr.next = null;
return dummy.next;
}
“两次遍历，两个列表，”商鞅傲然道，“虽非最优，却稳妥可靠。此乃我大秦治国之道——步步为营，稳中求胜！”
殿内一片寂静。
齐国算法宗师淳于髡抚须沉吟：“此解空间复杂度 O(n)，需额外存储…若链表长达万节点，恐内存不足。”
“那淳于先生可有妙解？”商鞅讥讽。
淳于髡苦笑摇头。他研习算法五十载，最擅“递归深搜”，对这种“原地修改”的迭代题，一时竟无良策。
第二幕：纨绔王子，醉语惊人
“父王，儿臣…嗝…儿臣有一解。”
懒洋洋的声音从殿门传来。
众人回头，只见一个锦衣青年倚着门框，手中金樽摇晃，酒气微醺。正是齐国七王子——姬玄。
他生得俊美，此刻却发髻松散，衣襟微敞，露出半截锁骨。眼角一枚泪痣，平添三分风流。
“玄儿！”齐威王怒拍扶手，“朝堂重地，成何体统！”
姬玄晃晃悠悠走进殿内，路过商鞅时，还打了个酒嗝：“秦使这解法…啧啧，O(n²)的时间，O(n)的空间…这要是在我齐国的‘算法武榜’上，怕是要排到万名开外。”
“狂妄！”商鞅脸色铁青，“七王子殿下，算法一道，靠的是真才实学，不是口舌之利！”
姬玄不理他，径直走到水镜前，伸手触摸。
**【系统提示】：检测到新解题者——齐国七王子姬玄】
【当前境界评估】：凡人境三层（疑似）】
【警告：醉酒状态可能影响思维】**
殿内响起窃窃私语。
“七王子整日流连‘风月楼’，也会算法？” “听说他上月还在‘算法启蒙堂’挂了科…” “怕是来胡闹的，丢尽我齐国脸面…”
宰相邹忌拱手道：“陛下，七王子宿醉未醒，不如…”
“让他试。”齐威王却突然开口，眼中闪过一丝复杂，“玄儿，你若解不出，罚禁足三月。”
姬玄笑了。
他仰头饮尽残酒，将金樽随手一抛——“铛啷”一声，清脆回响。
“不就是个 O(n) 的事儿嘛…”
第三幕：双指针现，震惊四座
姬玄指尖在水镜上轻划。奇怪的是，他明明醉眼朦胧，落指却精准无比。
class Solution {
public ListNode partition(ListNode head, int x) {
//“诸位请看，”姬玄不知从哪摸出两个锦囊，一红一蓝，”
//“这红囊，便是 dummy1，专收小于 x 的节点；
ListNode dummy1 = new ListNode(-1);
// 蓝囊，是 dummy2，专收大于等于 x 的节点。
ListNode dummy2 = new ListNode(-1);
//“现在，我派三个小厮。”姬玄拍拍手，仿佛真有三人，“p1 管红囊，p2 管蓝囊，p 负责从项链上取珍珠。”
ListNode p1 = dummy1, p2 = dummy2;
ListNode p = head;
while (p != null) {
//“p 取第一颗珍珠，数字 3，小于 x=5？是！给 p1，放入红囊...”
if (p.val >= x) {
p2.next = p;
p2 = p2.next;
} else {
//“第二颗，数字 8，大于等于 5？是！给 p2，放入蓝囊...”
p1.next = p;
p1 = p1.next;
}
// 但要先剪断珍珠间的丝线，防止纠缠。
ListNode temp = p.next;
p.next = null;
p = temp;
}
// 他又抽出一条珍珠项链，每颗珍珠都刻着数字——正是题目中的链表。
p1.next = dummy2.next;
return dummy1.next;
}
}
写罢，姬玄转身，对着满朝文武，开始讲解。
只是…他的讲解方式，实在奇特。 姬玄一边说，水镜一边生成动画。只见两个光囊悬浮，珍珠项链被一颗颗分类装入，行云流水，毫无滞涩。
商鞅瞪大了眼睛。
因为他看到了——只遍历一次。
第四幕：系统认证，天道金光
“最后，”姬玄拿起红蓝两个锦囊，将红囊的袋口与蓝囊的袋身相连，“红囊接蓝囊，大功告成！”
他话音方落——
“轰！”
水镜爆发出刺目金光！整个算法殿被映照得金碧辉煌。
【天道认证】
【新纪录诞生！】
【解法提供者：齐国七王子姬玄】
【时间复杂度：O(n)】
【空间复杂度：O(1)】
【击败率：100%】
【评价：惊才绝艳，开宗立派】
殿内死一般的寂静。
然后，哗然！
“O(1) 空间？！这…这怎么可能！”
“只遍历一次，同时完成分类和拼接？！”
“七王子他…他何时修得如此神通？！”
淳于髡颤抖着上前，老眼紧盯水镜上的代码：“虚拟头结点…双指针…原地修改…妙！妙啊！此解不仅高效，且完美保持节点相对顺序，断开原链接防止成环…简直是艺术！”
商鞅脸色煞白，踉跄后退。
他苦心钻研三个月的题目，被一个“纨绔王子”用一炷香时间，以碾压之势破解！
齐威王猛地站起，眼中精光爆射：“玄儿！你…你这是…”
姬玄却似浑不在意，懒懒伸个懒腰：“父王，儿臣昨夜做梦，有个白胡子老头教我的。他说这算法叫…嗯…‘阴阳双链分治诀’。”
【系统提示音在姬玄脑中响起】：
【叮！任务“链表分区”完成】 【奖励结算中…】
【金币+5000（已存入系统空间）】
【声望+1000（齐国声望+500，列国算法界声望+500）】
【获得称号：“链表圣手”（佩戴后链表类题目解题速度+20%）】
【解锁典籍：《算法导论·春秋特别版·第一卷》】
【新功能解锁：算法交易市场】
姬玄嘴角微翘。
穿越到这个“算法为尊”的春秋世界三个月，绑定“天机算法系统”两个月，装纨绔装了两个月零二十九天…今天，终于可以开始“收割”了。
第五幕：暗流涌动，佳人将至
当夜，七王子府邸。
姬玄躺在温泉池中，闭目查看系统界面。
【宿主：姬玄】
【境界：凡人境三层（伪装）/实际：才子境九层】
【掌握算法：链表操作（精通）、双指针（精通）、递归（熟练）…】
【金币：15200】
【声望：1250】
【当前任务：无】
【待领取：典籍×1，称号×1】
“领取典籍。”
光华一闪，手中多了一卷竹简。展开，却不是寻常文字，而是流动的代码光影。
// 《算法导论·春秋特别版·第一卷》
// 第一章：时间复杂度分析
// 第二章：空间复杂度优化
// 第三章：链表进阶技巧...
“有点意思。”姬玄正翻阅，忽然——
“殿下，有客到。”侍从在屏风外低语。
“谁？” “黑袍，遮面，说是…魏国商人。”
姬玄眼中闪过笑意：“来了。”
客厅内，黑袍人摘下兜帽，露出一张精明面孔：“在下魏国算法商人，白圭。奉魏王之命，特来拜会七王子。”
“为了白天的解法？”姬玄斜倚榻上，把玩着玉佩。
“正是！”白圭眼中放光，“殿下那‘阴阳双链分治诀’，魏王愿出万金购买专利！”
“不卖。” “…那，授权使用？每月抽成？” “可以考虑。”姬玄似笑非笑，“不过我听说，你们魏国最近在头疼‘合并K个有序链表’的军粮调度问题？”
白圭一震：“殿下如何得知？！”
这是魏国最高机密！为解决各城池军粮数据合并，魏国算法司已钻研月余，最佳解法仍需 O(nk) 时间。
姬玄从袖中取出一卷帛书：“O(n log k) 解法，要吗？”
白圭呼吸急促：“什…什么价？”
“钱？不要。”姬玄竖起两根手指，“一，我要你们魏国的‘优先队列’秘法原本。二…听说你们有个算法天才，叫庞涓？”
“庞先生是我魏国客卿…” “让他来齐国‘学术交流’三个月。”姬玄笑容灿烂，“放心，好吃好喝招待，说不定…他就不想回去了呢？”
白圭冷汗涔涔。
这是要挖魏国的墙角！
但…O(n log k) 的解法，足以让魏国军粮调度效率提升数倍！庞涓虽重要，但…
“我…我需要请示魏王。”
“给你三天。”姬玄摆手送客。
【系统】：触发支线任务“挖角庞涓”
【任务描述】：将魏国算法天才庞涓招揽至齐国
【奖励】：金币+10000，声望+2000，特殊道具“将星罗盘”
【失败惩罚】：魏国好感度-100
姬玄刚送走白圭，又一侍从来报：“殿下，楚国使团已至临淄，领队是…楚国公主，芈月。”
“芈月…”姬玄眯起眼。
系统资料显示：芈月，楚国第一算法天才，十六岁自创“芈氏递归法”，曾以 O(n) 空间解决“汉诺塔问题”，震惊列国。
更重要的是——她很美。
“公主殿下传话，”侍从神色古怪，“说明日‘算法学宫’交流，想与七王子…切磋‘二叉树直径’一题。”
姬玄笑了。
果然，出名了，麻烦和桃花都来了。
【系统】：新任务发布
【题目】：二叉树直径
【描述】：给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2]
输出：1
提示：
树中节点数目在范围 [1, 104] 内 -100 <= Node.val <= 100
【特殊要求】：使用递归，但空间复杂度须为 O(1)
【奖励】：若胜利，获得“芈月的好感度+50”，解锁“递归大师”称号
【额外提示】：芈月当前解法为 O(n²)，宿主可使用“Morris遍历法”碾压
“有意思。”姬玄走到窗边，望向夜空。
明月高悬，星河璀璨。
这个算法为尊的世界，比他想象的更有趣。而他的系统…似乎也隐藏着更深秘密。
“明天会一会这位楚国公主吧。”姬玄低声自语，“不过今晚…先看看这‘算法交易市场’是什么。”
他意念一动，系统界面变换——
【算法交易市场（测试版）】
【可出售】：
阴阳双链分治诀（O(n), O(1)） 标价：5000金币/国
双指针快慢判环法 标价：3000金币
递归转迭代通用技巧 标价：8000金币
【可购买】：
秦国的暴力美学（O(n²)系列算法） 售价：100金币（打折中）
楚国的递归秘典（第一卷） 售价：2000金币
鲁国的伦理算法约束条款 售价：500金币（姬玄：？？？）
“先把今天解法挂上去。”姬玄设置好价格，“定价…一万金币吧，反正列国有的是钱。”
【系统】：商品“阴阳双链分治诀”已上架 【提示】：已有7人加入收藏，3人咨询
姬玄满意点头，正要关闭系统，忽然——
“叮！”
【紧急通知】：检测到异常数据流
【来源】：秦国算法司
【内容】：疑似针对宿主明日的“二叉树直径”比试，篡改测试用例
【警告】：若使用常规递归解法，将在特定用例下栈溢出
姬玄眼神一冷。
“玩阴的？”
他调出“二叉树直径”题目详情，果然发现几个隐藏的“深链用例”——若递归深度超过10000层，普通解法必然崩溃。
“可惜…”姬玄笑了，“我有 Morris 遍历法，O(1) 空间，根本不怕深度。”
他想了想，在系统商城搜索“反制道具”。
【查找结果】：诚实卷轴（一次性）
【效果】：使目标在接下来一炷香内无法说谎
【售价】：300金币
【描述】：适用于辩论、审讯、以及…揭穿阴谋
“买了。”
光华闪过，一卷古朴卷轴落入手中。
姬玄把玩着卷轴，眼中寒光闪烁：“明天…就看看是谁在搞鬼。”
第六幕：学宫之约，暗藏杀机
次日，算法学宫。
齐国最高算法学府，此刻人山人海。不仅学子云集，连各国使节、江湖算法客都来围观——七王子姬玄 vs 楚国公主芈月，这噱头太大了。
姬玄到的时候，芈月已站在擂台上。
她一袭白衣，眉目如画，腰间系着楚国的“递归玉佩”，手中握一卷竹简。见姬玄来，微微颔首，眼神却带着审视。
“七王子殿下，”芈月声音清冷，“久仰。今日题目‘二叉树直径’，规则很简单：各写解法，水镜评判。胜者…可向败者提一个要求。”
台下哗然。
“公主这是把自己当赌注了？”
“姬玄王子若赢了，难道要公主…”
“休得胡言！公主算法通天，怎会输给一个纨绔？”
姬玄跃上擂台，笑道：“公主好魄力。不过…我若赢了，要求很简单：陪我在临淄城游玩三日，如何？”
芈月脸颊微红，却镇定道：“可以。但若我赢，你要当众承认——楚国算法，天下第一。”
“成交。”
水镜升起，题目显现。
姬玄正要动笔，忽然台下传来一声：“且慢！”
秦国使团中，走出一名青年，正是秦国年轻辈第一天才——嬴疾。
“此等盛事，岂可无公证？”嬴疾拱手，“在下提议，由我秦、魏、鲁三国各出一道测试用例，加入评判体系。如此，更显公平。”
姬玄心中冷笑：来了。
“可。”芈月不知有诈，点头应允。
嬴疾眼中闪过一丝得意，与魏、鲁两国代表各写下一个用例，投入水镜。
【系统提示】：新增三个隐藏测试用例
【深度】：12000层（秦）、15000层（魏）、18000层（鲁）
【效果】：递归深度超过10000层将触发栈溢出
芈月浑然不觉，开始解题。她用的是经典递归思路：
class Solution {
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return maxDiameter;
}
private int maxDepth(TreeNode node) {
if (node == null) return 0;
int left = maxDepth(node.left); // 递归左子树
int right = maxDepth(node.right); // 递归右子树
maxDiameter = Math.max(maxDiameter, left + right);
return Math.max(left, right) + 1;
}
}
“典型的后序遍历递归，”淳于髡在台下点评，“时间复杂度 O(n)，空间复杂度 O(n)（递归栈空间）。公主造诣确实深厚。”
芈月写罢，看向姬玄：“殿下，该你了。”
姬玄却不急，先走到嬴疾面前：“嬴兄，你那个测试用例…很深啊？”
嬴疾脸色微变：“殿下何意？”
“没什么，”姬玄忽然展开卷轴，“诚实卷轴，开！”
无形波动扩散，嬴疾眼神瞬间恍惚。
“告诉我，”姬玄声音低沉，“你那用例，是不是故意设了极深链条，想让我递归栈溢出？”
“是…”嬴疾不受控制地回答，“是商鞅大人吩咐…要让你在列国面前出丑…”
全场哗然！
“秦国竟如此卑鄙！”
“难怪主动要加测试用例！”
“无耻！”
商鞅脸色铁青：“嬴疾！你胡说什么！”
但诚实卷轴效果下，嬴疾继续爆料：“不止我…魏国和鲁国的用例，也是我们串通好的…”
魏国、鲁国代表慌忙低头。
芈月震惊地看着姬玄：“你…你怎么知道？”
“我自然有我的办法。”姬玄转身，面向水镜，“现在，公主看好了——什么才是真正的 O(1) 空间解法。”
他挥毫泼墨，写下了震惊整个算法界的代码：
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
int[] maxDiameter = new int[]{0};
morrisTraversal(root, maxDiameter);
return maxDiameter[0];
}
private void morrisTraversal(TreeNode root, int[] maxDiameter) {
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
// 无左子树，访问当前节点
process(curr, maxDiameter);
curr = curr.right;
} else {
// 找到前驱节点
TreeNode prev = curr.left;
while (prev.right != null && prev.right != curr) {
prev = prev.right;
}
if (prev.right == null) {
// 建立线索
prev.right = curr;
curr = curr.left;
} else {
// 拆除线索，访问当前节点
prev.right = null;
process(curr, maxDiameter);
curr = curr.right;
}
}
}
}
private void process(TreeNode node, int[] maxDiameter) {
// 计算以node为转折点的路径长度
int leftDepth = getDepth(node.left);
int rightDepth = getDepth(node.right);
maxDiameter[0] = Math.max(maxDiameter[0], leftDepth + rightDepth);
}
private int getDepth(TreeNode node) {
int depth = 0;
while (node != null) {
depth++;
node = node.left; // 沿着左子节点向下
}
return depth;
}
}
“这是…”芈月瞪大眼睛，“遍历中计算深度，无需递归…空间真的是 O(1)！”
水镜金光再起！
【天道认证】
【解法提供者：齐国七王子姬玄】
【时间复杂度：O(n)】
【空间复杂度：O(1)】
【评价：鬼斧神工，颠覆认知】
【特别备注：成功通过所有隐藏深度用例】
嬴疾瘫坐在地。商鞅拂袖而去。
芈月呆呆看着姬玄，良久，轻声道：“我输了。”
姬玄微笑：“那公主的承诺…”
“三日后，我来找你。”芈月深深看了他一眼，转身离去。只是…耳根有些红。
【系统】：任务“二叉树直径”完成
【奖励】：芈月好感度+50，当前好感度：60（好奇+钦佩）
【获得称号】：递归大师（递归类题目解题速度+30%）
【额外奖励】：揭露秦国阴谋，齐国声望+500
尾声：风起云涌
当夜，姬玄在府中清点收获时，系统突然弹出红色警告：
【紧急！】 【检测到异常算法波动】
【来源：齐国边境，稷下学宫遗址】
【内容：上古算法秘境“九章迷宫”即将开启】
【传闻：迷宫中藏有《九章算法》真迹，得之可突破圣人境】
【提示：列国天骄已动身】
几乎同时，侍从来报：“殿下，大王召见！说是…稷下学宫有异象！”
姬玄望向窗外。
东方天际，九道金光冲天而起，隐约构成九个篆文——正是“九章算法”四字。
“看来，”姬玄喃喃，“平静日子结束了。”
他打开系统界面，看着新跳出的任务：
【主线任务：探索九章迷宫】
【目标：获得《九章算法·第一卷》】
【竞争者】：秦国嬴驷、楚国芈月、魏国庞涓（疑似）、赵国廉颇…
【难度】：★★★★★
【奖励：未知（传说级）】
姬玄笑了。
“那就…去会会这天下英雄吧。”
他关闭系统，推门而出。月光洒落，照见他眼中燃烧的野望。
这个算法为尊的世界，他姬玄…要定了。
【下章预告】
第二章：九章迷宫，群雄逐鹿
核心算法：深度优先搜索 vs 广度优先搜索
关键冲突：迷宫中的“死锁”陷阱，如何用“拓扑排序”破局？
感情进展：姬玄与芈月被迫组队，黑暗中，她握住了他的手…
新人物：神秘少年“韩非”，自称来自“法家算法派”…
【本章算法知识点总结】
链表分区：双指针+虚拟头结点，O(n)时间O(1)空间
二叉树直径：Morris遍历法，O(n)时间O(1)空间
递归 vs 迭代：空间复杂度的本质区别
测试用例设计：边界条件的重要性
（读者可尝试自行实现上述算法，现实中链表分区是LeetCode第86题，二叉树直径是第543题，都是面试高频题哦！）
【作者说】 这就是第一章！将算法竞赛写成仙侠+权谋风格，大家觉得如何？明天更新第二章，会重点写DFS/BFS算法在迷宫探索中的应用，以及姬玄和芈月的互动。
如果喜欢这个风格，请告诉我，我会保持这种“每章一道算法题+剧情推进”的模式！
（P.S. 现实中遇到链表问题，真的推荐双指针法，优雅高效！）
