This is the 14th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

⚽ topic

Give you a linked list, remove the NTH node from the reciprocal of the list, and return the head node of the list.

Advanced: Can you try using a scan implementation?

Example 1:

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

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

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

Tip: The number of nodes in the list is sz1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
Copy the code

⚽ A little thought

I believe this kind of problem if the ordinary does not have this sentence ** can you try to use a scan to achieve? ** I think everyone can work it out. Don’t say there is a problem there is a problem back to the column themselves in the previous problem to do again, so add this sentence what should we do? I think it would be nice to know the length of the list which is pretty easy to do, but don’t you have to go through it one more time to get the length of the list, and then you get the NTH inverse. So here we have to think outside the box

• 1· The first method: construct a double pointer with two Pointers spaced n apart. When the last one reaches the tail, one is exactly the NTH reciprocal
• 2· The second kind: if you think the first kind of a bit loophole, the second kind can be a list of a traverse and then put into the stack, popup the n is to delete.The fatThat’s the way it’s done

⚽ open dry

⚽ Introduces a function Deque

A Deque isDouble ended queue (Dual-end queue)"Eggshell" is an abbreviation for "deck". Deque inherits from Queue and directly implements its LinkedList, ArayDeque, ConcurrentLinkedDeque, and so on. Deques support both limited capacity and unfixed size queues. Generally, the size of the two-end queue is uncertain. The Deque interface defines methods to access elements from the header and the tail. For example, insert, delete, and get elements at the head and tail, respectively. And the QueueCopy the code

The implementation class of Deque is divided into two main scenarios: the general scenario LinkedList variable size LinkedList dual-end queue, allowing elements to benullArrayDeque Specifies a large, variable array with a double-ended queuenullLinkedBlockingDeque If the queue is empty, the fetch operation will block until an element has been addedCopy the code

So now thatDequeinheritedQueueInterface so it must be able to do the queue, today we will only say it to do the use of the stack, say too long. Here are some of the ways it does stacks

⚽ source code and detailed

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
    // Create a new node pointing to the head node
        ListNode dummy = new ListNode(0, head);
        / / set up the stack
        Deque<ListNode> stack = new LinkedList<ListNode>();
        // This is a cursor variable used to traverse the list
        ListNode cur = dummy;
        // Push all the nodes in the list
        while(cur ! =null) {
            stack.push(cur);
            cur = cur.next;
        }
        // Exit the stack before the NTH
        for (int i = 0; i < n; ++i) { stack.pop(); ListNode prev = stack.peek(); ListNode prev = stack.peek(); prev.next = prev.next.next; ListNode ans = dummy.next;returnans; }}Copy the code

Ok, that’s all for today’s algorithm, we’ll see you tomorrow 🙂