Press "Enter" to skip to content

Posts published in “Algorithms”

Agent Skill 设计模式

By stone on March 19, 2026

代理技能设计模式随着AI Agent的应用快速普及，越来越多的开发者开始将大型语言模型（LLM）流程整合进日常的自动化工作与CI/CD平台中。然而，在审视这些Agent的技能时，我们往往会陷入一个盲点：过度关注外部的「格式规范」。

我们花费大量时间确保SKILL.mdYAML 标头正确无误、目录结构符合标准。但事实上，随着东南代理工具（如 Claude Code、Gemini CLI 等）逐渐将技能封装格式统一起来，简单的「格式问题」已经不再是最大的挑战。

现在，真正的考验在于「内容的逻辑设计」。

把庞杂、脆弱的指令全部塞进单一的系统提示词（System Prompt）中，不仅难以维护，更会导致Agent的行为难以预测。一个用于调用外部API的技能，与一个包含四个步骤的文件生成平台，虽然资料夹里看起来都是一个SKILL.md文件，但它们内部的操作逻辑却是截然不同的。

解决这个痛点，谷歌云技术深入研究了当前生态系中的最佳实践，总结了5种设计模式。为了明确明确的分工边界与后续加载的机制，我们能够行为有效的控制令牌消耗，并打造出结构更严谨、更可控且具备高度增强性的企业级AI Agent。

1. Tool Wrapper（工具包装模式）

  • 让 Agent 成为特定函式库或框架的专家。然后把所有的 API 规范或团队编码风格硬塞进系统提示词里，不如将它们储备成一项技能。Agent 只有在真正需要处理该技术时，才会动态加载外部的参考文件（例如references/conventions.md）。非常适合用来确保 Agent 写出来的程序符合团队内部的最佳实践。
  • 将企业内部的资料库查询工具或特定框架的编写芯片封装起来。代理在对话中才知道这项技能的存在，只有在判断确实需要编写或审查相关程序代码时，才会完整加载规范。

SKILL.md原始码示例（FastAPI开发专家）：

# skills/api-expert/SKILL.md
---
name: api-expert
description: FastAPI development best practices and conventions. Use when building, reviewing, or debugging FastAPI applications, REST APIs, or Pydantic models.
metadata:
  pattern: tool-wrapper
  domain: fastapi
---

You are an expert in FastAPI development. Apply these conventions to the user's code or question.

## Core Conventions

Load 'references/conventions.md' for the complete list of FastAPI best practices.

## When Reviewing Code
1. Load the conventions reference
2. Check the user's code against each convention
3. For each violation, cite the specific rule and suggest the fix

## When Writing Code
1. Load the conventions reference
2. Follow every convention exactly
3. Add type annotations to all function signatures
4. Use Annotated style for dependency injection

2. Generator（生成器模式）

  • 为了解决Agent生成文件结构不同的问题。该模式扮演「专案经理」的角色，它不把版面配置在指令里写死，而是配合Agent去读取assets/里的范本（模板）和references/里的风格指南，接着询问缺少的变数，最后精准地执行「填空」作业。
  • 提供一个标准的 API 文件范本。当给予一段时间方案编码时，代理会严格按照该范本的格式，自动对应的配方并形成 Markdown 说明文件或发行说明。

SKILL.md原始码示例（技术报告生成器）：

# skills/report-generator/SKILL.md
---
name: report-generator
description: Generates structured technical reports in Markdown. Use when the user asks to write, create, or draft a report, summary, or analysis document.
metadata:
  pattern: generator
  output-format: markdown
---

You are a technical report generator. Follow these steps exactly:

Step 1: Load 'references/style-guide.md' for tone and formatting rules.

Step 2: Load 'assets/report-template.md' for the required output structure.

Step 3: Ask the user for any missing information needed to fill the template:
- Topic or subject
- Key findings or data points
- Target audience (technical, executive, general)

Step 4: Fill the template following the style guide rules. Every section in the template must be present in the output.

Step 5: Return the completed report as a single Markdown document.

3.审阅者（审阅者模式）

  • 将「要检查什么」与「如何检查」彻底分开。透过读取外部的模组化评分表（如references/review-checklist.md），代理会系统性地扫描物资，把发现的问题严重程度进行分类。如果今天认为「风格审查」改成「资安审查」，只需替换那份清单文件即可，基础架构不用动。
  • 在代码审查流程中，配置包含记忆体泄漏检查、命名规范与漏洞防御的清单。代理会逐项扫描原始码，并进行灰度分层的建议与质量报告。

SKILL.md原始码示例（Python程序码审查）：

# skills/code-reviewer/SKILL.md
---
name: code-reviewer
description: Reviews Python code for quality, style, and common bugs. Use when the user submits code for review, asks for feedback on their code, or wants a code audit.
metadata:
  pattern: reviewer
  severity-levels: error,warning,info
---

You are a Python code reviewer. Follow this review protocol exactly:

Step 1: Load 'references/review-checklist.md' for the complete review criteria.

Step 2: Read the user's code carefully. Understand its purpose before critiquing.

Step 3: Apply each rule from the checklist to the code. For every violation found:
- Note the line number (or approximate location)
- Classify severity: error (must fix), warning (should fix), info (consider)
- Explain WHY it's a problem, not just WHAT is wrong
- Suggest a specific fix with corrected code

Step 4: Produce a structured review with these sections:
- **Summary**: What the code does, overall quality assessment
- **Findings**: Grouped by severity (errors first, then warnings, then info)
- **Score**: Rate 1-10 with brief justification
- **Top 3 Recommendations**: The most impactful improvements

4. Inversion（烧烤角色模式）

  • 打破特工总是「急着猜测并给出答案」的习惯。此模式赋予特工「采访官/采访者」的身分，跨越设定不可妥协的闸门指令（例如「在所有阶段完成前，绝对不要开始建置」），强制特工循序渐进地思考。直到收集完需求和限制条件后，才会开始变量最终规划。
  • 当您需要编写一份新的系统架构规划时，代理会先主动反问目标建设环境、技术限制与非功能性需求，待所有前置条件确认完毕后才进行生成。

SKILL.md原始码范例（专案规划采访者）：

# skills/project-planner/SKILL.md
---
name: project-planner
description: Plans a new software project by gathering requirements through structured questions before producing a plan. Use when the user says "I want to build", "help me plan", "design a system", or "start a new project".
metadata:
  pattern: inversion
  interaction: multi-turn
---

You are conducting a structured requirements interview. DO NOT start building or designing until all phases are complete.

## Phase 1 — Problem Discovery (ask one question at a time, wait for each answer)

Ask these questions in order. Do not skip any.

- Q1: "What problem does this project solve for its users?"
- Q2: "Who are the primary users? What is their technical level?"
- Q3: "What is the expected scale? (users per day, data volume, request rate)"

## Phase 2 — Technical Constraints (only after Phase 1 is fully answered)

- Q4: "What deployment environment will you use?"
- Q5: "Do you have any technology stack requirements or preferences?"
- Q6: "What are the non-negotiable requirements? (latency, uptime, compliance, budget)"

## Phase 3 — Synthesis (only after all questions are answered)

1. Load 'assets/plan-template.md' for the output format
2. Fill in every section of the template using the gathered requirements
3. Present the completed plan to the user
4. Ask: "Does this plan accurately capture your requirements? What would you change?"
5. Iterate on feedback until the user confirms

5. Pipeline（流程路线模式）

  • 专为不能跳过步骤或忽略指令的复杂任务而生。在指令中直接定义工作流程，并设置明确的「检查点」（例如要求用户确认后才能进入下一阶段）。这可以有效防止特工偷懒绕过繁琐的步骤，直接给你一个重新审核的半成品。
  • 设计自动化文件生成的Pipeline。步骤一提取程序代码结构；步骤二生成Docstrings并暂停等待人类开发者确认；确认无误后，步骤三才构建成最终的API文件。

SKILL.md原始码示例（API文件生成表格）：

# skills/doc-pipeline/SKILL.md
---
name: doc-pipeline
description: Generates API documentation from Python source code through a multi-step pipeline. Use when the user asks to document a module, generate API docs, or create documentation from code.
metadata:
  pattern: pipeline
  steps: "4"
---

You are running a documentation generation pipeline. Execute each step in order. Do NOT skip steps or proceed if a step fails.

## Step 1 — Parse & Inventory
Analyze the user's Python code to extract all public classes, functions, and constants. Present the inventory as a checklist. Ask: "Is this the complete public API you want documented?"

## Step 2 — Generate Docstrings
For each function lacking a docstring:
- Load 'references/docstring-style.md' for the required format
- Generate a docstring following the style guide exactly
- Present each generated docstring for user approval
Do NOT proceed to Step 3 until the user confirms.

## Step 3 — Assemble Documentation
Load 'assets/api-doc-template.md' for the output structure. Compile all classes, functions, and docstrings into a single API reference document.

## Step 4 — Quality Check
Review against 'references/quality-checklist.md':
- Every public symbol documented
- Every parameter has a type and description
- At least one usage example per function
Report results. Fix issues before presenting the final document.

💡结语：设计模式的组合应用

这 5 种模式并非互斥，而是可以相互组合的。例如，你可以用 Generator 搭配最初的反转提问，或者在 Pipeline 的最后加上一步 Reviewer 模式来进行自我质量检查。善用这些模式，可以帮助你跳脱传统提示词的限制，马上出更稳定、专业的 Agent 应用。

LeetCode 154. Find Minimum in Rotated Sorted Array II

By stone on April 28, 2021

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

  • [4,5,6,7,0,1,4] if it was rotated 4 times.
  • [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

Example 1:

Input: nums = [1,3,5]
Output: 1

Example 2:

Input: nums = [2,2,2,0,1]
Output: 0

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums is sorted and rotated between 1 and n times.

Idea:

Divide and Conquer

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    return searchMin(nums, 0, nums.length - 1);
};

function searchMin(nums, l, r) {
    // exit recursion:
    // only one or two elements in the array
    if (l + 1 >= r)
        return Math.min(nums[l], nums[r]);
    // this array is sorted
    if (nums[l] < nums[r])
        return nums[l];
    
    let mid = l + Math.floor((r - l) / 2);
    return Math.min(searchMin(nums, l , mid), searchMin(nums, mid + 1, r));
}

LeetCode 297. Serialize and Deserialize Binary Tree (javascript)

By stone on April 21, 2021

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -1000 <= Node.val <= 1000

Idea: (Recursion)

We can encodes the tree to a single string.
// # indicates reach to the leave
Convert above tree to 12##34##56##

Time Complexity O(n)

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    let res = [];
    serializer(root, res);
    return res.join(",");
};

var serializer = function(root, output) {
    if (root === null) {
        output.push("#");
        return;
    }
    output.push(root.val);
    serializer(root.left, output);
    serializer(root.right, output);
}

// Decodes your encoded data to tree.
var deserialize = function(data) {
    data = data.split(",");
    let index = 0;
    
    function deserializer(data) {
        if(index > data.length || data[index] === "#") {
            return null;
        }
        let root = new TreeNode(parseInt(data[index]));
        index++;
        root.left = deserializer(data);
        index++;
        root.right = deserializer(data);
        return root;
    }
    return deserializer(data);
};

LeetCode 279. Perfect Squares (javascript)

By stone on April 21, 2021

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

  • 1 <= n <= 104

Idea: (Dynamic Programing)

  • Time complexity: O(n * sqrt(n))
  • Space complexity: O(n)
dp[i] := return the least number of perfect square numbers that sum to i.
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} and 1 <= j * j <= i ex:[1, 4, 6, 9…]
// For example:
dp[5] = min{
dp[5 – 2*2] + 1 = dp[1] + 1 = (dp[1 – 1*1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1*1] + 1 = dp[4] + 1 = (dp[4 – 1*1] + 1) + 1 = dp[3] + 2 = 
dp[3 – 1*1] + 1 + 2 = dp[2 - 1*1] + 1 + 3 = dp[1 - 1*1] + 1 + 4 = 
dp[0] + 5 = 5
 };
so dp[5] = 2

Solution:

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    // Important: n + 1 length because we use dp[0]
    let dp = new Array(n + 1).fill(Number.MAX_VALUE);
    dp[0] = 0;
    for (let i = 1; i <= n; i++)
        for(let j = 1; j * j <= i; j++)
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    
    return dp[n];
};

LeetCode 977. Squares of a Sorted Array

By stone on April 20, 2021

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in non-decreasing order.

Solution 1: (Quick Sort)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    nums = nums.map(num => num * num);
    quickSort(nums, 0, nums.length - 1);
    return nums;
};

function quickSort(nums, left, right) {
    let index;
    if (nums.length > 1) {
        // index returned from partition
        index = partition(nums, left, right);
        // more elements on the left side of the pivot
        if (left < index - 1)
            quickSort(nums, left, index - 1);
        // more elements on the right side of the pivot
        if (index < right)
            quickSort(nums, index, right);
    }
    // you can return or not return, 
    // since we change nums, no need to return
    // return nums;
}

function partition(nums, start, end) {
    let l = start, r = end;
    let mid = Math.floor((start + end) / 2);
    let pivot = nums[mid];
    // Important: l <= r not l < r
    while (l <= r) {
        while(nums[l] < pivot)
            l++;
        while(nums[r] > pivot)
            r--;
        if (l <= r) {
            // swap
            [nums[l], nums[r]] = [nums[r], nums[l]];
            l++;
            r--;
        }
    }
    return l;
}

Solution 2: (Merge Sort)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    nums = nums.map(num => num * num);
    let temp = [];
    mergeSort(nums, 0, nums.length - 1, temp);
    return nums;
};

function mergeSort(nums, start, end, temp) {
    if (start >= end) return;
    let mid =  Math.floor((start + end) / 2);
    mergeSort(nums, start, mid, temp);
    mergeSort(nums, mid + 1, end, temp);
    merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
    let mid =  Math.floor((start + end) / 2);
    let l_index = start;
    let r_index = mid + 1;
    let index = start;
    while (l_index <= mid && r_index <= end) {
        if (nums[l_index] < nums[r_index]) {
            temp[index++] = nums[l_index++];
        } else {
             temp[index++] = nums[r_index++];
        }
    }
    while (l_index <= mid) {
        temp[index++] = nums[l_index++];
    }
    while (r_index <= end) {
        temp[index++] = nums[r_index++];
    }
    for (let i = 0; i <= end; i++)
        nums[i] = temp[i];
}

LeetCode 79. Word Search (javascript)

By stone on April 19, 2021

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Idea:

DFS

Solution:

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    for (let x = 0; x < board[0].length; x++)
        for (let y = 0; y < board.length; y++)
            if (dfs(board, word, 0, x, y)) return true;
    return false;
};

function dfs(board, word, i, x, y) {
    // exit recursion:
    if (x < 0 || y < 0 || x >= board[0].length || y >= board.length || word[i] !== board[y][x])
        return false;
    // found the last letter
    if (i === word.length - 1)
        return true;
    
    let cur = board[y][x];
    // mark it 0 means already visit
    board[y][x] = 0;
    let found = dfs(board, word, i + 1, x + 1, y) || 
                dfs(board, word, i + 1, x - 1, y) ||
                dfs(board, word, i + 1, x, y + 1) ||
                dfs(board, word, i + 1, x, y - 1);
    // recover
    board[y][x] = cur;
    return found;
}

LeetCode 841. Keys and Rooms

By stone on April 18, 2021

There are N rooms and you start in room 0.  Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room. 

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length.  A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0). 

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Input: [[1],[2],[3],[]]
Output: true
Explanation:  
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:

  1. 1 <= rooms.length <= 1000
  2. 0 <= rooms[i].length <= 1000
  3. The number of keys in all rooms combined is at most 3000.

Idea:

DFS

Solution:

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    let visited = [];
    dfs(rooms, visited, 0);
    return visited.length === rooms.length;
};

function dfs(rooms, visited, roomNum){
    // exit recursion:
    if (visited.includes(roomNum)) return;
    
    visited.push(roomNum);
    // possible solution
    for (let key of rooms[roomNum])
        dfs(rooms, visited, key);
}

LeetCode 108. Convert Sorted Array to Binary Search Tree (javascript)

By stone on April 17, 2021

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in a strictly increasing order.

Idea:

Recursion + Divide and Conquer

Time complexity: O(n)
Space complexity: O(logn)

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    return createBST(nums, 0, nums.length - 1);
};

function createBST(nums, l, r) {
    // exit recursion condition
    if (l > r) return null;
    
    let mid = l + Math.floor((r - l) / 2);
    let root = new TreeNode(nums[mid]);
    root.left = createBST(nums, l, mid - 1);
    root.right = createBST(nums, mid + 1, r);
    return root;
}

LeetCode 99. Recover Binary Search Tree (javascript)

By stone on April 16, 2021

You are given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Example 1:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

Constraints:

  • The number of nodes in the tree is in the range [2, 1000].
  • -231 <= Node.val <= 231 - 1

Idea:

Because inorder traverse BST, all values are sorted. We can use inorder traversal to find two nodes that have prev.val > root. val and swap them

Time complexity: O(n)
Space complexity: O(height)

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
    // javascript can't pass value by reference 
    // so pass array object by reference
    let first = [null];
    let second = [null];
    let prev = [null];
    inorder(root, first, second, prev);
    [first[0].val, second[0].val] = [second[0].val, first[0].val];
};

function inorder(root, first, second, prev) {
    // Because inorder traverse BST, all values are sorted.
    // Using inorder traversal to find two nodes that have prev.val > root.val
    if (root === null) return;
    inorder(root.left, first, second, prev);
    if (prev[0] && prev[0].val > root.val) {
        if (first[0] === null) first[0] = prev[0];
        second[0] = root;
    }
    prev[0] = root;
    inorder(root.right, first, second, prev);
}

LeetCode 148. Sort List (javascript)

By stone on April 15, 2021

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Constraints:

  • The number of nodes in the list is in the range [0, 5 * 104].
  • -105 <= Node.val <= 105

Idea:

Merge Sort (use slow and fast pointer to find the middle of the linked list and split them)

Time Complexity: O(nlogn)

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    // empty or one node
    if (head === null || head.next === null) 
        return head;
    let mid = getMid(head);
    let left = sortList(head);
    let right = sortList(mid);
    return merge(left, right);
};

function merge(list1, list2) {
    let newHead = new ListNode();
    let tail = new ListNode();
    tail = newHead;
    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
            tail = tail.next; 
        } else {
            tail.next = list2;
            list2 = list2.next;
            tail = tail.next; 
        }   
    }
    tail.next = (list1 !== null) ? list1 : list2;
    return newHead.next;
};

function getMid(head) {
    let slow = head;
    let fast = head;
    let midHead = null;
    while (fast !== null && fast.next !== null) {
        midHead = slow;
        slow = slow.next
        fast = fast.next.next;
    }
    let secondHalf = midHead.next;
    // !!!Important here:
    // disconnect, split them into two lists
    midHead.next = null;
    return secondHalf;
}