2025年｜牛客网剑指offer(更新中)

,

链表

从尾到头打印链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//3.从尾到头打印链表
//输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

function printListFromTailToHead(head){
    let arr = [];
    while(head){
        arr.push(head.val)
        head = head.next;
    }
    return arr.reverse();
}

// 递归
function printListFromTailToHead1(head){
    if(!head) return [];
    let result = printListFromTailToHead(head.next);
    result.push(head.val);
    return result;
}

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//15.反转链表
//输入一个链表，反转链表后，输出新链表的表头。

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function ReverseList(pHead){
    if(!pHead){
        return null;
    }
    let prev = null, cur = pHead, next;
    while(cur){
        next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

合并两个排序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//16.合并两个排序链表
//输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

function Merge(pHead1, pHead2){
    if(!pHead1) return pHead2;
    if(!pHead2) return pHead1;

    let list = null;
    if(pHead1.val > pHead2.val){
        list = pHead2;
        list.next = Merge(pHead1, pHead2.next);
    } else {
        list = pHead1;
        list.next = Merge(pHead1.next, pHead2);
    }
    return list;
}


两个链表的第一个公共结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 36.两个链表的第一个公共结点

function FindFirstCommonNode(pHead1, pHead2){
    let p1 = pHead1, p2 = pHead2;
    while(p1 !== p2){
        p1 = p1 ? p1.next : pHead2;
        p2 = p2 ? p2.next : pHead1;
    }
    return p1
}

function FindFirstCommonNode1(pHead1, pHead2){
    // write code here
    let p1 = pHead1;
    let p2 = pHead2;
    while(p1 != p2){
        p1 = (p1 == null) ? pHead2 : p1.next;
        p2 = (p2 == null) ? pHead1 : p2.next;
    }
    return p1;
}

链表中环的入口结点

1
2
3
4
5
6
7
8
9
10
11
12
13
//55.链表中环的入口结点
function EntryNodeOfLoop(pHead){
    let arr = [];
    while(pHead){
        if(arr.indexOf(pHead) !== -1){
            return pHead;
        } else {
            arr.push(pHead);
            pHead = pHead.next;
        }
    }
    return null;
}

链表中倒数最后k个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//14.链表中倒数第K个节点
//输入一个链表，输出该链表中倒数第k个结点。
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

function FindKthToTail(head, k){
    let arr = [];
    while(head){
        arr.push(head);
        head = head.next;
    }
    return arr[arr.length - k];
}

复杂链表的复制

1
2
3
4
5
6
7
8
9
10
//25.复杂链表的复制
function Clone(pHead){ 
    if(!pHead){
        return null;
        let h = new RandomListNode(pHead.label);
        h.random = pHead.random;
        h.next = Clone(pHead.next);
        return h;
    }
}

删除链表中重复的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function deleteDuplication(pHead){
    if(pHead == null || pHead.next == null) return pHead; // 只有0个或1个结点，则返回
    let pNode = pHead.next;
    if(pHead.val == pNode.val){
        while(pNode != null && pHead.val == pNode.val){
            pNode = pNode.next; // 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点
        }
        return deleteDuplication(pNode); // 从第一个与当前结点不同的结点开始递归
    } else {
        pHead.next = deleteDuplication(pNode);  // 当前结点不是重复结点,保留当前结点，从下一个结点开始递归
        return pHead;
    }
}

删除链表中的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

function deleteNode( head ,  val ) {
    // write code here
    //直接遍历，找到该节点，将pre和next节点连接在一起即可。
    //注意特殊输入，val是链表头端的情况;注意输入的val是值不是节点，与节点.val进行比较
    if(head.val===val) return head=head.next
    let cur = head
    let pre = null
    while(cur.val!==val){
        pre=cur
        cur=cur.next
    }
    pre.next=cur.next
    return head
}

树

二叉树的深度

1
2
3
4
5
6
7
function TreeDepth(pRoot){
    if(!pRoot) {
        return 0;
    } else {
        return Math.max(TreeDepth(pRoot.left), TreeDepth(pRoot.right)) + 1;
    }
}

按之字形顺序打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function Print(pRoot){
    if(!pRoot) return [];
    let queue = [], result = [], flag = true;
    queue.push(pRoot);
    while(queue.length){
        let len = queue.length;
        let temp = [];
        for(let i = 0; i < len; i++){
            let node = queue.shift();
            temp.push(node.val);
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
        if(!flag) temp.reverse();
        flag = !flag;
        result.push(temp);
    }
    return result;
}

二叉搜索树的第k个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function kthSmallest(root, k) {
    let count = 0;
    let result = null;
    
    function inorder(node) {
        if (!node || result) return;
        
        inorder(node.left);
        
        count++;
        if (count === k) {
            result = node;
            return;
        }
        
        inorder(node.right);
    }
    
    inorder(root);
    return result;
}

重建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//4.重建二叉树
//输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */

function reConstructBinaryTree(pre, vin) {
    if(pre.length === 0 || vin.length === 0) return null;
    let k = pre[0];
    let index = vin.indexOf(k);
    let root = new TreeNode(k);
    root.left = reConstructBinaryTree(pre.slice(1, index + 1), vin.slice(0, index));
    root.right = reConstructBinaryTree(pre.slice(index + 1), vin.slice(index + 1));
    return root;
}

树的子结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//17.树的子结构
//输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */

function HasSubtree(pRoot1, pRoot2){
    if(!pRoot1 || !pRoot2) return false;
    return find(pRoot1, pRoot2) || HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2); 
}

function find(pRoot1, pRoot2){
    if(!pRoot2) return true;
    if(!pRoot1 || pRoot1.val !== pRoot2.val) return false;
    return find(pRoot1.left, pRoot2.left) && find(pRoot1.right, pRoot2.right);
}

二叉树的镜像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//18.二叉树的镜像
//操作给定的二叉树，将其变换为源二叉树的镜像。
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */

function Mirror(pRoot) {
    if(root){
        [pRoot.left, pRoot.right] = [pRoot.right, pRoot.left];
        Mirror(pRoot.left);
        Mirror(pRoot.right);
    }
    return pRoot;
}

从上到下打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//22.从上往下打印二叉树
function PrintFromTopToBottom(root) {
    let arr = [];
    let data = [];
    if(root){
        arr.push(root);
    }
    while(arr.length){
        let node = arr.shift();
        if(node.left){
            arr.push(node.left);
        }
        if(node.right){
            arr.push(node.right);
        }
        data.push(node.val);
    }
    return data;
}

二叉搜索树的后序遍历序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//23.二叉搜索树的后序遍历序列
/**
 * 验证序列是否为二叉搜索树的后序遍历结果
 * @param {number[]} sequence - 后序遍历序列
 * @return {boolean}
 */
function verifySequenceOfBST(sequence) {
    if (!sequence || sequence.length === 0) {
        return true; // 空序列或空树视为有效
    }
    
    return verify(sequence, 0, sequence.length - 1);
    
    function verify(arr, start, end) {
        if (start >= end) {
            return true; // 只有一个节点或无节点
        }
        
        // 根节点是最后一个元素
        const root = arr[end];
        
        // 寻找左子树和右子树的分界点
        let i = start;
        while (i < end && arr[i] < root) {
            i++; // 左子树所有节点都小于根
        }
        
        // 检查右子树是否都大于根
        let j = i;
        while (j < end) {
            if (arr[j] < root) {
                return false; // 右子树有小于根的值
            }
            j++;
        }
        
        // 递归验证左右子树
        return verify(arr, start, i - 1) && verify(arr, i, end - 1);
    }
}

二叉树中和为某一值的路径（-）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//24.二叉树中和为某一值的路径
let r,p
function FindPath(root, expectNumber){
    // write code here
    r = []
    p = []
    if(!root){return r};
    cal(root,expectNumber)
    return p
}
function cal(root,exp){
    r.push(root.val);
    if(root.val == exp && !root.left&& !root.right){
        p.push(r.slice())
    }else{
        if(root.left) cal(root.left,exp - root.val);
        if(root.right) cal(root.right,exp - root.val);
    }
    r.pop()
}

二叉树搜索树与双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 递归方法（中序遍历）
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

/**
 * 将二叉搜索树转换为排序双向链表（递归方法）
 * @param {TreeNode} root - 二叉搜索树的根节点
 * @return {TreeNode} - 双向链表的头节点
 */
function treeToDoublyList(root) {
    if (!root) return null;
    
    let head = null;   // 链表头节点
    let prev = null;   // 前一个节点
    
    // 中序遍历
    function inorder(node) {
        if (!node) return;
        
        // 遍历左子树
        inorder(node.left);
        
        // 处理当前节点
        if (prev) {
            // 前一个节点的right指向当前节点
            prev.right = node;
            // 当前节点的left指向前一个节点
            node.left = prev;
        } else {
            // 第一个节点，记录为头节点
            head = node;
        }
        
        // 更新prev为当前节点
        prev = node;
        
        // 遍历右子树
        inorder(node.right);
    }
    
    inorder(root);
    
    // 连接首尾节点形成循环双向链表
    if (head && prev) {
        head.left = prev;
        prev.right = head;
    }
    
    return head;
}

判断是不是平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//39.平衡二叉树
function IsBalanced_Solution(pRoot) {
    if(!pRoot) return true;
    let left = getDepth(pRoot.left);
    let right = getDepth(pRoot.right);
    if(Math.abs(left - right) > 1) {
        return false;
    } else {
        return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
    }
}

function getDepth(root) {
    if(!root) return 0;
    let left = getDepth(root.left);
    let right = getDepth(root.right);
    return Math.max(left, right) + 1;
}

二叉树的下一个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function GetNext(pNode) {
    if(pNode.right){
        pNode = pNode.right;
        while(pNode.left){
            pNode = pNode.left;
        }
        return pNode;
    }
    while(pNode.next){
        let pRoot = pNode.next;
        if(pRoot.left == pNode){
            return pRoot;
        }
        pNode = pRoot;
    }
    return null;
}

对称的二叉树

1
2
3
4
5
6
7
8
9
10
11
12
//58.对称的二叉树
function isSymmetrical(pRoot) {
    if(!pRoot) return true;
    return find(pRoot.left, pRoot.right);
}

function find(pRoot1, pRoot2) {
    if(!pRoot1 && !pRoot2) return true;
    if(!pRoot1 || !pRoot2) return false;
    return pRoot1.val == pRoot2.val && find(pRoot1.left, pRoot2.right) && find(pRoot1.right, pRoot2.left);
}

把二叉树打印成多行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//60.把二叉树打印成多行
function Print(pRoot) {
    let result = [], queue = [];
    if(!pRoot) return result;
    queue.push(pRoot);
    while(queue.length){
        let vertical = [];
        let len = queue.length;
        for(let i = 0; i < len; i++){
            let temp = queue.shift(); //front
            vertical.push(temp.val);
            if(temp.left){
                queue.push(temp.left);
            }
            if(temp.right){
                queue.push(temp.right);
            }
        }
        result.push(vertical);
    }
    return result;
}

序列化二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

/**
 * 先序遍历序列化二叉树
 * @param {TreeNode} root - 二叉树根节点
 * @return {string} - 序列化后的字符串
 */
function serialize(root) {
    const result = [];
    
    function preorder(node) {
        if (!node) {
            result.push('#');
            return;
        }
        
        result.push(node.val.toString());
        preorder(node.left);
        preorder(node.right);
    }
    
    preorder(root);
    return result.join(',');
}

/**
 * 先序遍历反序列化二叉树
 * @param {string} data - 序列化字符串
 * @return {TreeNode} - 反序列化后的二叉树根节点
 */
function deserialize(data) {
    if (!data) return null;
    
    const values = data.split(',');
    let index = 0;
    
    function build() {
        if (index >= values.length) return null;
        
        const val = values[index];
        index++;
        
        if (val === '#') return null;
        
        const node = new TreeNode(Number(val));
        node.left = build();
        node.right = build();
        
        return node;
    }
    
    return build();
}

在二叉树中找到两个节点的最近公共祖先(TODO)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 递归查找最近公共祖先
 * @param {TreeNode} root - 二叉树根节点
 * @param {TreeNode} p - 节点p
 * @param {TreeNode} q - 节点q
 * @return {TreeNode} - 最近公共祖先
 */
function lowestCommonAncestor(root, p, q) {
    if (!root || root === p || root === q) {
        return root;
    }
    
    // 在左子树中查找
    const left = lowestCommonAncestor(root.left, p, q);
    // 在右子树中查找
    const right = lowestCommonAncestor(root.right, p, q);
    
    // 如果左右子树都找到了节点，说明当前节点是LCA
    if (left && right) {
        return root;
    }
    
    // 否则返回非空的那个
    return left || right;
}

二叉搜索树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

/**
 * 递归查找二叉搜索树的最近公共祖先
 * @param {TreeNode} root - 二叉搜索树根节点
 * @param {TreeNode} p - 节点p
 * @param {TreeNode} q - 节点q
 * @return {TreeNode} - 最近公共祖先
 */
function lowestCommonAncestorBST(root, p, q) {
    // 确保p.val <= q.val
    if (p.val > q.val) {
        [p, q] = [q, p];
    }
    
    // 递归查找
    return findLCA(root, p, q);
}

function findLCA(node, p, q) {
    if (!node) return null;
    
    // 如果当前节点值大于q，说明两个节点都在左子树
    if (node.val > q.val) {
        return findLCA(node.left, p, q);
    }
    
    // 如果当前节点值小于p，说明两个节点都在右子树
    if (node.val < p.val) {
        return findLCA(node.right, p, q);
    }
    
    // 当前节点值在p和q之间，或者等于p或q，就是LCA
    return node;
}

队列和栈

用两个栈实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//5.用两个栈实现一个队列
//用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
let a = [];
let b = [];
function push(node){
    // write code here
    a.push(node)
}
function pop(){
    // write code here
    if(b.length==0){ //当b空的时候
        while(a.length){
            b.push(a.pop())
        } 
    }
    return b.pop()  //b空和不空的时候
}

包含min函数的栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//20.包含min函数的栈
//定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
let arr = []
function push(node){
    // write code here
    arr.push(node)
}
function pop(){
    // write code here
    return arr.pop()
}
function top(){
    // write code here
    return arr.length==0 ? null : arr[arr.length-1]
}
function min(){
    // write code here
    return Math.min(...arr)  
}

栈的弹出、压入序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//21.栈的弹出、压入序列
function IsPopOrder(pushV, popV){
    // write code here
    let stack=[];
    let N=pushV.length;
    let j=0
    for(let i=0;i<N;i++){
        stack.push(pushV[i]);
        while(j<N&&popV[j]==stack[stack.length-1]&&stack.length!=0){
              stack.pop();
              j++;
        }
    }
    return stack.length==0;
}

翻转单词序列

1
2
3
4
5
//44.翻转单词顺序列
function ReverseSentence(str){
    // write code here
    return str.split(' ').reverse().join(' ')
}

滑动窗口的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * 暴力解法 - O(n*k)
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function maxSlidingWindowBruteForce(nums, k) {
    if (!nums || nums.length === 0 || k <= 0) return [];
    if (k === 1) return nums;
    
    const n = nums.length;
    const result = [];
    
    for (let i = 0; i <= n - k; i++) {
        let max = nums[i];
        for (let j = 1; j < k; j++) {
            if (nums[i + j] > max) {
                max = nums[i + j];
            }
        }
        result.push(max);
    }
    
    return result;
}

/**
 * 使用双端队列（单调递减队列） - O(n)
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function maxSlidingWindow(nums, k) {
    if (!nums || nums.length === 0 || k <= 0) return [];
    if (k === 1) return nums;
    
    const n = nums.length;
    const result = [];
    const deque = []; // 存储索引，保证队首到队尾是递减的
    
    for (let i = 0; i < n; i++) {
        // 1. 移除超出窗口范围的元素
        if (deque.length > 0 && deque[0] < i - k + 1) {
            deque.shift();
        }
        
        // 2. 维护单调递减队列
        // 从队尾开始，移除所有小于当前元素的索引
        while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }
        
        // 3. 将当前索引加入队列
        deque.push(i);
        
        // 4. 当窗口形成时，记录窗口最大值
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }
    
    return result;
}

参考内容

github上offer answer