“This is the 14th day of my participation in the First Challenge 2022.

Leetcode-19 Removes the NTH node from the list

Subject to introduce

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

Example 1

Enter: head = [1.2.3.4.5], n = 2Output:1.2.3.5]
Copy the code

Example 2

Enter: head = [1], n = 1Output: []Copy the code

Example 3

Enter: head = [1.2], n = 1Output:1]
Copy the code

Tip:

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

Their thinking

Idea 1: Double traversal

Double traversal refers to traversing the list twice. The first traversal of the whole list can obtain the length of the whole list. Then, to obtain the penultimate NTH node, we only need to traverse the list from the beginning, and then go forward the length of the list -n steps to reach the last node of the node to be deleted. You can delete the NTH node from the penultimate list by pointing the next pointer to the node to be deleted

The problem solving steps

1. Define a virtual head nodenewNode(in case the node to be deleted is the head node of the linked list), the virtual head nodenextPoint to the actual head node
2. definepThe pointer traverses from the virtual head node,kUsed to record the length of a linked list
3. ifp.nextNot empty, willpPoint to thep.nextAnd thenk++
4. After recording the list length in step 3, thepPointer repoints to the virtual head node of the linked listnewNodeAnd thenpThe needle goes forwardk - nStep to the last node of the node to be deleted
5. willpPointer to a nodenextPointer top.next.nextTo delete the node to be deleted
6. Returns the next node of the virtual head node

The problem solving code

var removeNthFromEnd = function(head, n) {
    // Define a virtual head node
    const newNode = new ListNode(-1, head)
    // Define a pointer to the virtual head node
    let p = newNode, k = 0
    // Get the length of the list
    while (p.next) {
        p = p.next
        k++ 
    }
    // the p pointer points to the virtual head node
    p = newNode
    // The distance from the p node to the node before the deletion
    let step = k - n
    // Go to the node before the deleted node
    while (step--) {
        p = p.next
    }
    // Delete the penultimate node
    p.next = p.next.next
    // return the head node
    return newNode.next
};
Copy the code

Idea 2: double pointer method

Two Pointers can be used. The first pointer takes n steps before the second pointer, and then the two Pointers move forward at the same time. When the fast pointer reaches the end of the list, the node that the slow pointer points to is the last node of the node to be deleted

The problem solving steps

1. Define a virtual head nodenewNode(in case the node to be deleted is the head node of the linked list), the virtual head nodenextPoint to the actual head node
2. Defining fast PointersnextAnd slow pointerpreAlso start with the virtual head node
3. Quick pointernextTo go forwardn 步
4. The fast and slow hands move forward at the same time until the fast handsnextGo to the end of the list
5. willpreOf the node pointing tonextPointer topre.next.next
6. Returns the next node of the virtual head node

The problem solving code

var removeNthFromEnd = function(head, n) {
    // Create a virtual head node
    const newNode = new ListNode(-1, head)
    // Define two Pointers to the virtual head node
    let pre = next = newNode
    // The fast pointer moves forward n positions
    while (n--) {
        next = next.next
    }
    // The fast pointer and the slow pointer move at the same time. When the fast pointer reaches the end, the slow pointer points to the node before the deleted node
    while (next.next) {
        pre = pre.next
        next = next.next
    }
    // Set the next node of the slow pointer to the next node of the deleted node
    pre.next = pre.next.next
    // return the head node
    return newNode.next
};
Copy the code

So far, we have removed the NTH node from the list in two ways