DAILY DOCDAILY DOC
Rust
Node
Notes
Ubuntu
Leetcode
  • it-tools
  • excalidraw
  • linux-command
Rust
Node
Notes
Ubuntu
Leetcode
  • it-tools
  • excalidraw
  • linux-command
  • Array

    • 数组
    • 二分查找
    • moveZeros
  • Dynamic-programming

    • 动态规划
  • 刷题指南
  • String

    • 字符串
  • bitwise-operator

    • 位运算符
  • heap
  • history

    • [1014] 最佳观光组合
    • [1022] 从根到叶的二进制数之和
    • [104] 二叉树的最大深度
    • [11] 盛最多水的容器
    • [110] 平衡二叉树
    • [1227] 飞机座位分配概率
    • [129] 求根节点到叶节点数字之和
    • [1306] 跳跃游戏 III
    • [148] 排序链表
    • 155.最小栈
    • [165] 比较版本号
    • 1763. 最长的美好子字符串
    • [1870] 准时到达的列车最小时速
    • [199] 二叉树的右视图
    • [21] 合并两个有序链表
    • 215.数组中的第 k 个最大元素
    • [2306] 公司命名
    • [234] 回文链表
    • [2516] 每种字符至少取 K 个
    • [316] 去除重复字母
    • [3171] 找到按位或最接近 K 的子数组
    • [322] 零钱兑换
    • [41] 缺失的第一个正数
    • [44] 通配符匹配
    • [494] 目标和
    • [509] 斐波那契数
    • [518] 零钱兑换 II
    • [62] 不同路径
    • [676] 实现一个魔法字典
    • 70 爬楼梯
    • [718] 最长重复子数组
    • [78] 子集
    • [82] 删除排序链表中的重复元素 II
    • [871] 最低加油次数
    • [88] 合并两个有序数组
    • [887] 鸡蛋掉落
    • 958.二叉树的完全性检验
    • [98] 验证二叉搜索树
    • [983] 最低票价
    • leetcode practice
    • 约瑟夫问题
    • 移除重复节点
  • linked-list

    • 706. 设计哈希映射
    • 链表
  • stack

    • stack
  • tree

    • Tree Traversal
    • 二叉树的最近公共祖先
    • 二叉树
    • 题目
  • leetCode 刷题
  • 回溯
  • 排序算法

链表

details
class LinkNode {
    constructor(val, next = null) {
        this.value = val;
        this.next = next;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }
    insert(val) {
        if (this.head === null) {
            this.head = new LinkNode(val);
            return;
        }
        // find the last node
        let current = this.head;
        while (current.next !== null) {
            current = current.next;
        }
        // next pointer to the new node
        current.next = new LinkNode(val);
    }
    delete(val) {
        if (!this.head) return;
        // head
        if (this.head.value === val) {
            this.head = this.head.next;
            return;
        }

        let current = this.head;
        while (current.next !== null && current.next.value !== val) {
            current = current.next;
        }
        // middle
        if (current.next !== null) {
            current.next = current.next.next;
        }
        // tail
    }
    find(val) {
        let current = this.head;
        while (current !== null) {
            if (current.value === val) {
                return current;
            }
            current = current.next;
        }

        return null;
    }
    toArray() {
        const result = [];
        let current = this.head;
        while (current !== null) {
            result.push(current.value);
            current = current.next;
        }
        return result;
    }
}

function traverse_linear(head) {
    const result = [];
    let current = head;
    while (current !== null) {
        result.push(current.value);
        current = current.next;
    }
    return result;
}
function traverse_linear_for(head) {
    const result = [];
    for (let node = head; node !== null; node = node.next) {
        result.push(node.value);
    }
    return result;
}

function traverse_recursive(head) {
    let result = [];
    traverse(head);

    function traverse(node) {
        if (!node) return;
        result.push(node.value);
        traverse(node.next);
    }
    return result;
}

142. 环形链表 II

HashSet

HashSet 缓存遍历过的节点

Javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
    const visited = new Set();
    while (head !== null) {
        if (visited.has(head)) {
            return head;
        }
        visited.add(head);
        head = head.next;
    }
    return null;
};

快慢指针

相遇点,快指针比慢指针多走了一倍的路程。相当于从起点到入环的距离等于相遇点到入环的距离,因此,可以定义一个新指针 p 从 head 开始走,slow 跟 p 相遇的时候就是环起点。

Javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
    if (!head || !head.next) return null;
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            let start = head;
            while (start !== slow) {
                start = start.net;
                slow = slow.next;
            }
            return start;
        }
    }

    return null; // 没有环
};

141. 环形链表

快慢指针

Javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
    if (!head || !head.next) return false;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            return true; // 环存在
        }
    }

    return false; // 没有环
};

202. 快乐数

hash 表

Javascript
/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
    const visited = new Set();
    while (n !== 1 && !visited.has(n)) {
        visited.add(n);
        n = getNext(n);
    }
    return n === 1;

    function getNext(n) {
        let sum = 0;
        while (n > 0) {
            let d = n % 10;
            n = (n / 10) >> 0;
            sum += d ** 2;
        }
        return sum;
    }
};

快慢指针

Javascript
/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
    let slow = n,
        fast = getNext(n);
    while (fast !== 1 && slow !== fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    return fast === 1;

    function getNext(n) {
        let sum = 0;
        while (n > 0) {
            let d = n % 10;
            n = (n / 10) >> 0;
            sum += d ** 2;
        }
        return sum;
    }
};

206. 反转链表

迭代

Javascript
/**
 * 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 reverseList = function (head) {
    if (head === null) return head;
    let cur = head,
        prev = null;

    while (cur !== null) {
        let next = cur.next;

        cur.next = prev;
        prev = cur;

        cur = next;
    }
    return prev;
};

递归

Javascript
var reverseList = function (head) {
    return traverse(head, null);

    function traverse(cur, prev) {
        if (cur === null) return prev;
        let next = cur.next;
        cur.next = prev;
        return traverse(next, cur);
    }
};

92. 反转链表 II

Javascript
var reverseBetween = function (head, left, right) {
    // 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论
    const dummyNode = new ListNode(-1);
    dummyNode.next = head;

    let pre = dummyNode;
    // 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点
    // 建议写在 for 循环里,语义清晰
    for (let i = 0; i < left - 1; i++) {
        pre = pre.next;
    }

    // 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点
    let rightNode = pre;
    for (let i = 0; i < right - left + 1; i++) {
        rightNode = rightNode.next;
    }

    // 第 3 步:切断出一个子链表(截取链表)
    let leftNode = pre.next;
    let curr = rightNode.next;

    // 注意:切断链接
    pre.next = null;
    rightNode.next = null;

    // 第 4 步:同第 206 题,反转链表的子区间
    reverseLinkedList(leftNode);

    // 第 5 步:接回到原来的链表中
    pre.next = rightNode;
    leftNode.next = curr;
    return dummyNode.next;
};

const reverseLinkedList = head => {
    let pre = null;
    let cur = head;

    while (cur) {
        const next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
};

1019. 链表中的下一个更大节点

单调栈

Javascript
/**
 * 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 {number[]}
 */
var nextLargerNodes = function (head) {
    const stack = [];
    const result = [];
    let i = 0;

    while (head) {
        result.push(0);

        while (stack.length && stack[stack.length - 1].val < head.val) {
            const node = stack.pop();
            result[node.index] = head.val;
        }

        stack.push({ val: head.val, index: i });
        i++;
        head = head.next;
    }

    return result;
};
Rust
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}
struct Solution {}
impl Solution {
    fn next_larger_nodes(head: Option<Box<ListNode>>) -> Vec<i32> {
        let mut result = Vec::new();
        let mut stack = Vec::new();

        let mut current = &head;
        while let Some(node) = current {
            while !stack.is_empty() && node.val > result[*stack.last().unwrap()] {
                let idx = stack.pop().unwrap();
                result[idx] = node.val;
            }
            stack.push(result.len());
            result.push(node.val);
            current = &node.next;
        }

        for idx in stack {
            result[idx] = 0;
        }

        result
    }
}

Last Updated:
Contributors: rosendo
Prev
706. 设计哈希映射