8 篇博文 含有标签「链表」

1、题干​

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例 2：

输入：root = []
输出：[]

提示：

• 树中的节点数在范围 [0, 6000] 内
• -100 <= Node.val <= 100

进阶：

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。

2、思路​

BFS模拟，每一层的节点用一个队列存储，队列中节点的 next 指向下一个节点即可。

这题没有 Rust 编码环境。。

3、代码​

function connect(root: Node | null): Node | null {
    let queue: Node[] = root ? [root] : [];

    while (queue.length) {
        const nextQueue = [];
        for (let i = 0; i < queue.length; i++) {
            queue[i].next = queue[i + 1];
            if (queue[i].left) nextQueue.push(queue[i].left);
            if (queue[i].right) nextQueue.push(queue[i].right);
        }
        queue = nextQueue;
    }

    return root;
};

1、题干​

给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。

下图中蓝色边和节点展示了操作后的结果：

请你返回结果链表的头指针。

示例 1：

输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

示例 2：

输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释：上图中蓝色的边和节点为答案链表。

提示：

• 3 <= list1.length <= 104
• 1 <= a <= b < list1.length - 1
• 1 <= list2.length <= 104

2、思路​

题目不难，根据题意模拟就行，唯一需要注意的边界是 a = 0 的情况

3、代码​

function mergeInBetween(list1: ListNode | null, a: number, b: number, list2: ListNode | null): ListNode | null {
    let node1 = null, node2 = null;

    for (let i = 0, node = list1; node; i++, node = node.next) {
        if (i === a - 1) node1 = node;
        if (i === b) node2 = node.next;
    }

    for (let node = list2; node !== node2; node = node.next) {
        if (!node.next) node.next = node2;
    }

    return !node1 ? list2 : (node1.next = list2, list1);
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。

实现 Solution 类：

• Solution(ListNode head) 使用整数数组初始化对象。
• int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

示例：

输入
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]

解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。

提示：

• 链表中的节点数在范围 [1, 104] 内
• -104 <= Node.val <= 104
• 至多调用 getRandom 方法 104 次

进阶：

• 如果链表非常大且长度未知，该怎么处理？
• 你能否在不使用额外空间的情况下解决此问题？

2、解题思路​

数组存储所有节点值，getRandom 时使用随机数 API 生成随机序号并返回数组内相应的值。

3、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

4、代码​

var Solution = function (head) {
    this.list = [];
    while (head) {
        this.list.push(head.val);
        head = head.next;
    }
};

Solution.prototype.getRandom = function () {
    return this.list[Math.floor(Math.random() * this.list.length)];
};

5、执行结果​

1、题干​

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

示例 1：

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：

输入的多级列表如下图所示：



扁平化后的链表如下图：

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

  1---2---NULL
  |
  3---NULL

示例 3：

输入：head = []
输出：[]

如何表示测试用例中的多级链表？

以 示例 1 为例：

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

序列化其中的每一级之后：

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

合并所有序列化结果，并去除末尾的 null 。

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

提示：

• 节点数目不超过 1000
• 1 <= Node.val <= 10^5

执行结果​

解题思路​

• 使用栈存储后续需要遍历的节点，先压入node.next再压入node.child
• 当栈内元素不为空时，弹出栈顶元素进行处理
• 当前节点属于以下2种情况需特殊处理（代码中的link()函数）：
  • 1、child有值：将当前节点与子节点转成兄弟节点，并将当前节点的child置位空
  • 2、next和child为空值：将当前节点与栈顶节点转成兄弟节点，并将当前节点的child置位空

代码​

var flatten = function (head) {
    const link = (cur, next) => (cur.next = next, cur.child = null, next.prev = cur);
    let node, stack = [head];

    while (node = stack.pop()) {
        if (node.next) stack.push(node.next);
        if (node.child) stack.push(node.child), link(node, node.child);
        if (!node.next && !node.child && stack.length) link(node, stack[stack.length - 1]);
    }

    return head;
};

1、题干​

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

示例 1：

输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。

示例 2：

输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。

示例 3：

输入：head = [1], insertVal = 0
输出：[1,0]

提示：

• 0 <= Number of Nodes <= 5 * 10^4

• -10^6 <= Node.val <= 10^6

• -10^6 <= insertVal <= 10^6

执行结果​

解题思路​

• 1、head为空，创建一个新链表返回即可
• 2、head不为空，在中间位置（即node.next.val >= insertVal >= node.val）插入新节点
• 3、head不为空，没有中间位置，则遍历一轮找到最大值节点，在最大值节点后方插入新节点

代码​

var insert = function (head, val) {
    let node = head, maxNode = head;
    while (node) {
        if (node.val >= maxNode.val) maxNode = node;
        if (val >= node.val && val <= node.next.val) break;
        if (head === node.next) { node = maxNode; break; }
        node = node.next;
    }
    if (node) node.next = new Node(val, node.next);

    if (!head) head = new Node(val), head.next = head;
    return head;
};

1、题干​

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

示例 1：

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：

输入的多级列表如下图所示：



扁平化后的链表如下图：

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

  1---2---NULL
  |
  3---NULL

示例 3：

输入：head = []
输出：[]

如何表示测试用例中的多级链表？

以 示例 1 为例：

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

序列化其中的每一级之后：

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

合并所有序列化结果，并去除末尾的 null 。

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

提示：

• 节点数目不超过 1000
• 1 <= Node.val <= 10^5

执行结果​

解题思路​

• 使用栈存储后续需要遍历的节点，先压入node.next再压入node.child
• 当栈内元素不为空时，弹出栈顶元素进行处理
• 当前节点属于以下2种情况需特殊处理（代码中的link()函数）：
  • 1、child有值：将当前节点与子节点转成兄弟节点，并将当前节点的child置位空
  • 2、next和child为空值：将当前节点与栈顶节点转成兄弟节点，并将当前节点的child置位空

代码​

var flatten = function (head) {
    const link = (cur, next) => (cur.next = next, cur.child = null, next.prev = cur);
    let node, stack = [head];

    while (node = stack.pop()) {
        if (node.next) stack.push(node.next);
        if (node.child) stack.push(node.child), link(node, node.child);
        if (!node.next && !node.child && stack.length) link(node, stack[stack.length - 1]);
    }

    return head;
};

1、题干​

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

示例 1：

输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。

示例 2：

输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。

示例 3：

输入：head = [1], insertVal = 0
输出：[1,0]

提示：

• 0 <= Number of Nodes <= 5 * 10^4

• -10^6 <= Node.val <= 10^6

• -10^6 <= insertVal <= 10^6

执行结果​

解题思路​

• 1、head为空，创建一个新链表返回即可
• 2、head不为空，在中间位置（即node.next.val >= insertVal >= node.val）插入新节点
• 3、head不为空，没有中间位置，则遍历一轮找到最大值节点，在最大值节点后方插入新节点

代码​

var insert = function (head, val) {
    let node = head, maxNode = head;
    while (node) {
        if (node.val >= maxNode.val) maxNode = node;
        if (val >= node.val && val <= node.next.val) break;
        if (head === node.next) { node = maxNode; break; }
        node = node.next;
    }
    if (node) node.next = new Node(val, node.next);

    if (!head) head = new Node(val), head.next = head;
    return head;
};

1、题干​

链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。

如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个  局部极大值点 。

如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个  局部极小值点 。

注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。

给你一个链表 head ，返回一个长度为 2 的数组 [minDistance, maxDistance] ，其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回 [-1，-1] 。

示例 1：

输入：head = [3,1]
输出：[-1,-1]
解释：链表 [3,1] 中不存在临界点。

示例 2：

输入：head = [5,3,1,2,5,1,2]
输出：[1,3]
解释：存在三个临界点：
- [5,3,1,2,5,1,2]：第三个节点是一个局部极小值点，因为 1 比 3 和 2 小。
- [5,3,1,2,5,1,2]：第五个节点是一个局部极大值点，因为 5 比 2 和 1 大。
- [5,3,1,2,5,1,2]：第六个节点是一个局部极小值点，因为 1 比 5 和 2 小。
第五个节点和第六个节点之间距离最小。minDistance = 6 - 5 = 1 。
第三个节点和第六个节点之间距离最大。maxDistance = 6 - 3 = 3 。

示例 3：

输入：head = [1,3,2,2,3,2,2,2,7]
输出：[3,3]
解释：存在两个临界点：
- [1,3,2,2,3,2,2,2,7]：第二个节点是一个局部极大值点，因为 3 比 1 和 2 大。
- [1,3,2,2,3,2,2,2,7]：第五个节点是一个局部极大值点，因为 3 比 2 和 2 大。
最小和最大距离都存在于第二个节点和第五个节点之间。
因此，minDistance 和 maxDistance 是 5 - 2 = 3 。
注意，最后一个节点不算一个局部极大值点，因为它之后就没有节点了。

示例 4：

输入：head = [2,3,3,2]
输出：[-1,-1]
解释：链表 [2,3,3,2] 中不存在临界点。

提示：

• 链表中节点的数量在范围 [2, 105] 内
• 1 <= Node.val <= 105

代码​

/**
 * 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 nodesBetweenCriticalPoints = function (head) {
    let [minDistance] = [Infinity];
    let [i, count, firstIndex, preIndex] = [0, 0, -1, -1];
    let preNode = head;
    head = head.next;
    
    while (head) {
        if (!head.next) break;

        if ((head.val > preNode.val && head.val > head.next.val) || (head.val < preNode.val && head.val < head.next.val)) {
            if (firstIndex < 0) firstIndex = i;
            if (preIndex >= 0) minDistance = Math.min(i - preIndex, minDistance);

            preIndex = i;
            count++;
        }

        preNode = head;
        head = head.next;
        i++;
    }

    return count < 2 ? [-1, -1] : [minDistance, preIndex - firstIndex];
};