更改我的链表实现以解决 Leetcode 问题？

Question

我正在研究这个 leetcode 问题：https://leetcode.com/problems/delete-node-in-a-linked-list/

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

我找到了这个解决方案：

var deleteNode = function (node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

这是我的链表实现：

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor(value) {
        const newNode = new Node(value);
        this.head = newNode;
        this.tail = this.head;
        this.length = 1;
    }
}

我不知道为什么它在我的 LL 实现上不起作用。

Answer 1

在引用的问题中，只使用了这个节点 class。这是 Leet 代码在注释块中显示的内容：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

第一个问题是 val 属性在您的 class 中被称为 value，因此您应该在 [=14] 中更改该名称=]代码。

其次，Leet Code 不引入也不需要链表 class，因此这意味着您在 LinkedList 实例中拥有的所有数据都必须保持更新你会用一个节点做什么 class，就像上面的那个。

实际上，通过添加具有自己属性的 LinkedList class，您还会遇到一个额外的问题：调用 deleteNode(node) 时，您必须确保node 实际上是你的链表实例中的一个节点，而不是其他链表中的一个节点。如果你有两个链表怎么办？您如何知道作为参数传递给 deleteNode 的节点属于哪个列表？

现在如果我们可以假设 node 参数是您当前链表中的一个节点，我们可以将 deleteNode 定义为一个方法。

旁注：您的 LinkedList 构造函数会立即创建一个节点，但这是一个坏主意：链表可以为空，因此从一个空列表开始（默认情况下），并使用通常的加法添加第一个节点的方法。

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        // A linked list could be empty, so don't create a node
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    append(val) {  // 
        if (!this.tail) this.head = this.tail = new Node(val);
        else this.tail = this.tail.next = new Node(val);
        this.length++;
    }
    deleteNode(node) {
        node.value = node.next.value; // Use value, not val
        node.next = node.next.next;
        // Also update the linked list properties:
        if (!node.next) this.tail = node;
        this.length--;
    }
    *[Symbol.iterator]() { // A generator to easily output the list's values
        for (let node = this.head; node; node = node.next) {
            yield node.value;
        }
    }
}

// demo
const list = new LinkedList(); 
list.append(1);
list.append(2);
list.append(3);
console.log("initial list:  ", ...list);
list.deleteNode(list.head.next); // Delete the 2
console.log("after deletion:", ...list);

更改我的链表实现以解决 Leetcode 问题？

Change my Linked List implentation to work on Leetcode problems?

javascript

implementation

linked-list

data-structures