Change my Linked List implentation to work on Leetcode problems?

Question

I'm working on this leetcode problem: 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.

and I've found this solution:

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

This is my Linked List implementaion:

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;
    }
}

I dont't know why it's not working on my LL implemetation.

Answer 1

In the referenced question there is just this node class being used. This is what Leet Code shows in a comment block:

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

The first issue is that the val property is called value in your class, so you should change that name where it occurs in the deleteNode code.

Secondly, Leet Code does not introduce nor need a linked list class, so that means that all the data you have in your LinkedList instance, will have to be kept updated on top of what you would do with just a node class, like the one above.

Actually, by adding a LinkedList class with its own properties, you'll have an additional problem: when deleteNode(node) is called, you'll have to be sure that node is actually a node in your linked list instance, and not in some other linked list. What if you have two linked lists? How will you know to which list the node belongs that is passed as argument to deleteNode?

Now if we can assume that the node argument is a node in your current linked list, we can define deleteNode as a method.

A side note: your LinkedList constructor immediately creates a node, but this is a bad idea: linked lists can be empty, so start with an empty list (by default), and use the usual addition method(s) to also add the first node.

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);