LeetCode removes the NTH node from the list – JavaScript

The title

Title link: leetcode-cn.com/leetbook/re…

Answer key

1. Delete the given node by traversing twice

To delete linked list nodes, the general idea is to find the previous node to be deleted, and then delete the node to be deleted. Here, the linked list is first traversed to get the length of the list, and then traversed to the previous node of the self-defined node to delete the given node.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} n
 * @return {ListNode}* /
var removeNthFromEnd = function(head, n) {

    let len = 0;
    let temp = head;

    // Get the list length
    while(temp ! = =null) {
        len++;
        temp = temp.next;
    }
    
    // Handle the case of deleting the first node
    if(n === len) {
        return head.next;
    }

    // Find the node before the specified location node, and delete the specified node
    len = len - n;
    temp = head;
    for(let i = 2; i <= len; i++) { temp = temp.next; } temp.next = temp.next.next;// memory is automatically reclaimed in js, as long as references to objects are removed;

    return head;
};
Copy the code

Pay attention to the boundary condition, when deleting the first node, because there is no head node in the linked list, it is not consistent with deleting other nodes. Therefore, additional operations should be performed on deleting the first node.

2. Delete the specified node using a traversal

Space for time is a universal law;

If we want to delete the specified node in one traversal, we can store the addresses of all nodes by using an array first.

Then, the random access of the sequential array is used to directly obtain the previous node of the specified node.

Finally, delete the specified node.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} n
 * @return {ListNode}* /
var removeNthFromEnd = function(head, n) {

    let len = 0;
    let temp = head;

    let addressArr = [];

    while(temp ! = =null) {

        len++;
        addressArr.push(temp);
        temp = temp.next;
    }

    // Handle the case of deleting the first node
    if(n === len) {
        return head.next;
    }

    addressArr[len - n - 1].next = addressArr[len - n].next;
    addressArr = null;

    return head;
};
Copy the code

3. Use recursion

You can also use recursive implementation, exit the recursive stack process count, so that you can realize the reciprocal count to delete the specified node; Pay attention to what happens when the node to be deleted is the first node;

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} n
 * @return {ListNode}* /
var removeNthFromEnd = function(head, n) {
    // This flag is used when the node to be deleted is the first one, so that it can be processed later
    let flag = false;

    function deleteNode(initialHead,head,n) {

        if(head === null) {return n;
        }

        m = deleteNode(initialHead,head.next,n);

        if(m === 0) {
            head.next = head.next.next;
        }else if(m === 1 && head === initialHead) {  // When the node to be deleted is the last one
           
            flag = true; 
            return ;
        }
        
        
        return m -1;
    }

    deleteNode(head,head,n); // When you write js, you define a function and forget to execute it...

    if(flag) {
        head = head.next;
    }

    return head;
};
Copy the code

4. Add top nodes to the list for unified operation

The absence of a header node in a linked list causes an inconsistency in deletion operations, so add a header node to the list node first, and then use the above method to process the list.

Here is the code for adding the first node to the list and then iterating through it twice to remove the node:

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} n
 * @return {ListNode}* /
var removeNthFromEnd = function(head, n) {

    const vhead = new ListNode(null,head);

    let len = 0;
    let temp = head;

    // Get the list length
    while(temp ! = =null) {
        len++;
        temp = temp.next;
    }
    

    // Find the node before the specified location node, and delete the specified node
    len = len - n;
    temp = vhead;
    for(let i = 1; i <= len; i++) { temp = temp.next; } temp.next = temp.next.next;// memory is automatically reclaimed in js, as long as references to objects are removed;


    return vhead.next;
};

Copy the code

If you have a better way of thinking and reconciliation, welcome to discuss ah ~

This is a summary and implementation of each problem in LeetCode’s “Elementary Algorithms” using JavaScript. The summary is here:

Juejin. Cn/post / 700669…