This is the 20th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

The title

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

Train of thought

In a linked list data structure, there are several cases when you want to delete the node at the NTH position

  • Delete the head node, simply point the reference of the head node to the byte point of the head node, head = head.next

  • Delete the intermediate Node, and reference the child Node of the Node in the n-1 position to the child Node of the NTH Node, namely Node(n-1).next = Node(n).next

  • The deleted node is the last node, and the reference to the child node of the node at position N-1 needs to be null

Note, however, that the problem is to delete the penultimate node, that is, to delete len-n node. According to this idea, we can first calculate the length of the list len, and then walk through the list once, when len-n positions are reached, delete the operation

The following code

    /** * 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 h = head;
        let len = 0;

        // Calculate the list length
        while(h) {
            h = h.next;
            len++;
        }

        // Delete the header node
        if(len == n) {
            head = head.next;
            return head;
        }

        h = head;

        // Find the node before the node to delete
        for(let i = 0; i < len - n - 1; i++) {
            h  = h.next;
        }
        h.next = h.next.next;

        return head;
    };
Copy the code

thinking

The above solution, to calculate the length of the linked list, traverses the list completely once, and traverses the list again when looking for the node before the deleted node. Is there a way to traverse just once to find the node before the deleted node?

Double pointer: you can define two Pointers, left and right. Initially, both Pointers point to the head node. But let the right pointer take n steps, and then let the two Pointers take n steps at the same time. When right gets to the end of the list, the left pointer points to len-n nodes

But from the solution of the two traversals above, what we really need to find is the len-n-1 node. In this case, we can add an empty node before the head node, so that the double pointer gets len-n-1 nodes, and then delete the head node

The following code

    /** * 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) {
        // Add an empty node to the header
        let h = new ListNode(null, head);
        // Define two Pointers
        let left = h, right = h;
        // The right pointer goes first
        for(let i = 0; i < n; i++) {
            right = right.next;
        }

        // When right comes to the end
        while(right.next) {
            right = right.next;
            left = left.next;
        }

        // Delete a node
        left.next = left.next.next;

        // Delete the header node
        h = h.next;

        return h;
    };
Copy the code

summary

The double pointer algorithm mentioned above, also known as fast and slow pointer, is more suitable for the list to find the penultimate node problem

LeetCode 👉 HOT 100 👉 Delete the NTH node from the list

LeetCode 👉 HOT 100 👉 Letter combination of phone number – medium question ✅

LeetCode 👉 HOT 100 👉 Sum of three numbers – medium question ✅

LeetCode 👉 HOT 100 👉 Container that holds the most water – medium title ✅

LeetCode 👉 HOT 100 👉 longest loop string – medium ✅

LeetCode 👉 HOT 100 👉 The oldest string without repeating characters – medium ✅

LeetCode 👉 HOT 100 👉 add two numbers – medium ✅

LeetCode 👉 HOT 100 👉 sum of two numbers – easy question ✅