The title

Leetcode-cn.com/problems/re… 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?

Train of thought

This idea is also very simple, is fast or slow pointer. Let the fast pointer take n steps first, and then the slow pointer takes n steps. When the fast pointer =null, the slow pointer is the NTH node from the bottom. Note:

1. The discriminant condition is fast==null

2, while is greater than 0

3. What the title requires is to delete the NTH node. The one-way linked list has no pre pointer but only Next, so it is difficult to delete.

4, but 3 will also appear a problem is that when the linked list has only one element, find the first to the last, in this case n+1=2 will exceed the bounds, so we need to use a pseudo-head node dummyhead. Finally, dummyhead.next is output

code

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null){
            return null;
        }
        ListNode dummyhead = new ListNode(0);
        dummyhead.next = head;
        ListNode fast = dummyhead;
        ListNode slow = dummyhead;
        n = n + 1;
        while(n-->0){
            fast=fast.next;
        }
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummyhead.next;

    }
}
Copy the code