在给定位置插入双向链表的所有情况在 JS 中都不起作用

Question

我已经使用 javascript 在节点的开头、中间和结尾添加了一个在给定位置插入的双向链表插入程序，所以问题是：所有测试用例都不能正常工作，就像输入 3 一样。 2 4 5 2 6 我的输出是 2 6 4 5，预期输出是 2 4 5 6，所以您能否纠正我的错误并进行修改，以便所有边缘情况在这里都可以正常工作？ head、pos 和 data 是起始指针。 pos表示要在哪个位置进入新节点，data是新数据。代码如下。 输入： 链表：2<->4<->5 p = 2，x = 6 输出：2 4 5 6 解释：p = 2，x = 6。因此，6 是 插入到 p 之后，即位置 3

输入： 链表：1<->2<->3<->4 p = 0，x = 44 输出：1 44 2 3 4 解释： p = 0，x = 44 。所以，44 插入到 p 之后，即位置 1

class Solution {
    addNode(head, pos, data) {
        const newHead = { data: data, prev: null, next: null }; 

        if (head === null) {
            return newHead; 
        }
        let temp = head;
        for (let i = 1; i < pos - 1 && temp.next !== null; i++) {
            temp = temp.next;
        }

        if (pos > 1 && temp === null) {
            return head;
        }

        newHead.next = temp.next;
        if (temp.next !== null) {
            temp.next.prev = newHead;
        }

        temp.next = newHead;
        newHead.prev = temp;

        return head;
    }
}

Answer 1

这里有几个问题：

• for

  循环没有进行足够的迭代来满足

  pos

  的定义。例如，如果

  pos

  为 1，则循环应进行一次迭代，以便

  temp

  引用第二个节点（位于索引 1 处）。

• 循环后的

  if

  语句检查

  pos

  的值，就好像它在循环中发生了变化，但显然它没有。此外，这意味着如果

  pos

  小于 2，并且

  temp

  恰好是

  null

  ，则在访问

  temp.next

  时会遇到错误。此

  if

  条件不应检查

  pos

  的值。

• 没有规定可以在列表的前面插入节点以使其成为第一个节点。根据

  pos

  的解释，您必须传递值 -1 才能在列表前面插入新节点，但您的代码没有针对这种情况的规定。

• 列表为空和非空时行为不一致。当它为空时，您的代码不会验证

  pos

  参数，但是当列表不为空且

  pos

  的值太大时，您的函数不会追加新节点。这并不一致。当列表为空并且要插入第一个节点时，您还应该进行此检查。根据上述观察，当您想要插入第一个节点时，

  pos

  的值应为 -1。

这是对上面列出的点进行更正的代码：

    addNode(head, pos, data) {
        const newHead = { data: data, prev: null, next: null }; 

        if (pos == -1) { // Insert at start
            newHead.next = head;
            if (head) {
                head.prev = newHead;
            }
            return newHead;
        }
        
        if (!head) { // Invalid value for pos argument
            return head; 
        }
        
        let temp = head;
        // Number of iterations corrected
        for (let i = 0; i < pos && temp.next; i++) {
            temp = temp.next;
        }

        // Check only temp
        if (!temp) { // Invalid value for pos argument
            return head;
        }

        newHead.next = temp.next;
        if (temp.next) {
            temp.next.prev = newHead;
        }

        temp.next = newHead;
        newHead.prev = temp;

        return head;
    }

最后评论：这是指定

pos

的不常见方式。如果

pos

反映新节点插入列表后将具有的索引，那就更有意义了。因此，

pos

应该比您当前指定的规格多 1。