This is the 16th day of my participation in Gwen Challenge

preface

The penultimate node of the linked list is deleted as follows:

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

Advanced: Can you try using a scan implementation?

Example 1:

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

Example 2:

Input: head = [1], n = 1 output: []

Example 3:

Input: head = [1,2], n = 1

A, thinking

This is a very intuitive idea. First go through the linked list and record the total number of the linked list. Then start from the beginning and find the nodes that need to be deleted. This idea is in scheme one, order 2N.

So how do you optimize?

In fact, if you want to go over and over and find the NTH element, the key is to record the position of the NTH element

So how do we find this location? In fact, you can use the fast and slow pointer, first let the fast pointer take N steps, then the fast and slow Pointers go together, and when the fast pointer ends, the slow pointer points to the NTH element from the bottom.

Graphic fast and slow Pointers

The yellow pointer indicates the fast pointer and the green pointer indicates the slow pointer

As shown below, the red square represents the NTH element from the bottom (tips: Take the third element from the bottom here)

Let the fast pointer take N steps first, that is, 3 steps first, and the result is as follows:

Then the fast and slow Pointers go down together, and the final result is shown in the figure below:

It is not difficult to find that when the fast pointer goes to the end, the slow pointer now points to the element before the NTH element from the penultimate. At this point, you can set the slow pointer to the next node, removing the NTH element from the penultimate list

The pseudocode is as follows:

ListNode slow;  / / pointer to slow
slow.next = slow.next.next;
Copy the code

Second, the implementation

Option 1 (Count)

The implementation code here takes the force of the official ~ (please forgive TNT)

Code implementation

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while(head ! =null) {
            ++length;
            head = head.next;
        }
        return length;
    }
Copy the code

Scheme 2 (Fast and slow pointer)

Code implementation

Tips: When initializing, both the fast and slow Pointers point to the head of the list

   /** ** ** /
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first = head;  / / pointer
        ListNode second = head; / / pointer to slow
        while(first.next ! =null) {
            first = first.next;
            if (n <= 0)
                second = second.next;
            n --;
        }
        if (n == 1)
            return second.next;
        second.next = second.next.next;
        return head;
    }
Copy the code

The test code

The test code is shown below

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1.new ListNode(2.new ListNode(3.new ListNode(4.new ListNode(5)))));
// ListNode listNode = new ListNode(1, new ListNode(2));
        new Number19().removeNthFromEnd(listNode, 5);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥