“This is the 19th day of my participation in the December Gwen Challenge. See details: 2021 Last Gwen Challenge”

Delete the NTH node from the list

Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.

Example 1: 

Input: head = [1,2,3,4,5], n = 2Copy the code

Example 2:

Input: head = [1], n = 1 output: []Copy the code

Example 3:

Input: head = [1,2], n = 1Copy the code

Tip:

  • The number of nodes in the linked list is zerosz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Advanced: Can you try using a scan implementation?

recursive

Train of thought

Using recursive thinking: Here we define three variables,

  • Pre is used to save the previous node before deleting the node,

  • Next is used to save the next node after the deleted node,

  • Index is used to record the current penultimate node

Next = next and then return the head node

If pre does not exist, the head node is deleted, return head.next

var removeNthFromEnd = function (head, n) {
    var pre = null
    var next = null
    var index = 0
    function remove(head, n) {
        if(! head) { index++return
        }
        remove(head.next, n)
        
        if (index === n) {
            next = head.next
        }
        if (index === n + 1) {
            pre = head
        }
        index += 1
    }
    remove(head, n)

    if (pre) {
        pre.next = next
        return head
    } else {
        return head.next
    }
};
Copy the code

Hash table idea

Train of thought

So here we’re going to store it in an array and we’re going to go through every node of the list and we’re going to get the array ARR

Find the pre node and the next node as above

  • The subscript of the n node to be deleted is arr. Leng -n

  • So the subscript of the pre node is arr.length-n-1

  • The subscript of the next node is arr.length-n+1

It should be noted that the n node should be deleted after pre and Next are found, because deleting the N node in advance will affect the search for the subscripts of Pre and Next, leading to errors, so it is deleted at the end

Finally, check to see if there are any values in the array, and return the first node if there are, or null otherwise

var removeNthFromEnd = function (head, n) {
    var pre = null
    var next = null
    var arr = []
    while (head) {
        arr.push(head)
        head = head.next
    }
    if (arr[arr.length - n + 1]) {
        next = arr[arr.length - n + 1]}if (arr[arr.length - n - 1]) {
        pre = arr[arr.length - n - 1]
        pre.next = next
    }
    arr.splice(arr.length - n, 1)
    var res = arr[0]? arr[0] : null
    return res

};
Copy the code